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.     int result=INT_MIN;
  11.  
  12.     for(int i=0;i<n;i++){
  13.         for(int j=0;j<m;j++){
  14.             dp[i][j]=A[i]*B[j];
  15.  
  16.             for(int p=0;p<=i-1;p++){
  17.                 for(int q=0;q<=j-1;q++){
  18.                     dp[i][j]=max(dp[i][j],A[i]*B[j]+dp[p][q]);
  19.                 }
  20.             }
  21.  
  22.             result=max(result,dp[i][j]);
  23.         }
  24.     }
  25.  
  26.     return result;
  27. }
  28.  
  29. int main(){
  30.     int n,m;
  31.     cin>>n>>m;
  32.     vector<int>A(n);
  33.     vector<int>B(m);
  34.  
  35.     for(int i=0;i<n;i++){
  36.         cin>>A[i];
  37.     }
  38.     for(int j=0;j<m;j++){
  39.         cin>>B[j];
  40.     }
  41.  
  42.     int result=solve_dp(A,B);
  43.     cout<<"Maximum score possible : "<<result<<endl;
  44.     return 0;
  45. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 
6 
0 1 5 4 2
0 6 7 2 1 100
stdout
copy 
Maximum score possible : 507
https://ideone.com/VeoTYA
language:
C++ (gcc 8.3)
created:
15 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!