fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 2007;
  6.  
  7. int prefA[MAXN];
  8. int prefB[MAXN];
  9. int DP[MAXN][MAXN];
  10.  
  11.  
  12. int main(){
  13.     ios_base::sync_with_stdio(0);
  14.     cin.tie(0);
  15.     cout.tie(0);
  16.     int n, m, x;
  17.     cin >> n >> m;
  18.     //sumy prefiksowe obu talerzy
  19.     for(int i = 1; i <= n; i++){
  20.         cin >> x;
  21.         prefA[i] = prefA[i-1]+x;
  22.     }
  23.     for(int i = 1; i <= m; i++){
  24.         cin >> x;
  25.         prefB[i] = prefB[i-1]+x;
  26.     }
  27.  
  28.     //dynamik
  29.     //bierzemy wszystkie nalesniki z obu stosow i odejmujemy najgorszy wynik jesli jeden z gornych nalesnikow jest zabrany
  30.     for(int i = 0; i <= n; i++){
  31.         for(int j = 0; j <= m; j++){
  32.             if(i==0 && j==0){
  33.                 DP[i][j] = 0;
  34.             }else if(i == 0){
  35.                 DP[i][j] = prefA[i] + prefB[j] - DP[i][j-1];
  36.             }else if(j == 0){
  37.                 DP[i][j] = prefA[i] + prefB[j] - DP[i-1][j];
  38.             }else{
  39.                 DP[i][j] = prefA[i] + prefB[j] - min(DP[i-1][j], DP[i][j-1]);
  40.             }
  41.             cout << i << " " << j << " " << DP[i][j] << "\n";
  42.         }
  43.     }
  44.  
  45.     cout << DP[n][m] << "\n";
  46.     return 0;
  47. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
3 3
2 7 -5
10 -2 -3
stdout
copy 
0 0 0
0 1 10
0 2 -2
0 3 7
1 0 2
1 1 10
1 2 12
1 3 0
2 0 7
2 1 12
2 2 5
2 3 14
3 0 -3
3 1 17
3 2 7
3 3 2
2
https://ideone.com/QbYVJD
language:
C++ (gcc 8.3)
created:
3 days 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!