fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int solve_dp(vector<int>&A,vector<int>&B){
  6.     int n=A.size();
  7.     int m=B.size();
  8.  
  9.     vector<vector<int>>dp(n,vector<int>(m,0));
  10.     vector<vector<int>>dp2(n,vector<int>(m,0));
  11.  
  12.     int result=INT_MIN;
  13.  
  14.     for(int i=0;i<n;i++){
  15.         for(int j=0;j<m;j++){
  16.             dp[i][j]=A[i]*B[j];
  17.  
  18.  
  19.             for(int p=0;p<=i-1;p++){
  20.                 dp2[i][j]=max(dp2[i][j],dp[p][j]);
  21.             }
  22.  
  23.             for(int q=0;q<=j-1;q++){
  24.                 dp[i][j]=max(dp[i][j],A[i]*B[j]+dp2[i][q]);
  25.             }
  26.  
  27.             result=max(result,dp[i][j]);
  28.         }
  29.     }
  30.  
  31.     return result;
  32. }
  33.  
  34. int main(){
  35.     int n;
  36.     cin>>n;
  37.     int m;
  38.     cin>>m;
  39.  
  40.     vector<int>A(n);
  41.     vector<int>B(m);
  42.  
  43.     for(int i=0;i<n;i++){
  44.         cin>>A[i];
  45.     }
  46.     for(int i=0;i<m;i++){
  47.         cin>>B[i];
  48.     }
  49.  
  50.     int ans=solve_dp(A,B);
  51.     cout<<"Maximum score: "<<ans<<endl;
  52.     return 0;
  53. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
5 
6
0 1 5 4 2 
0 6 7 2 1 100
stdout
copy 
Maximum score: 507
https://ideone.com/1Kex3l
language:
C++ (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!