Advertisement
YEZAELP

PROG-1148: Sushi

Mar 29th, 2021 (edited)
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 2e9;
  5. using pi = pair <int, int>;
  6. int n, m, k;
  7. int L[20010];
  8. int P[20010];
  9. vector < vector <int>> dp(20010, vector <int> (2, -INF));
  10.  
  11. int main(){
  12.  
  13.     scanf("%d%d%d", &n, &m, &k);
  14.  
  15.     for(int i=1;i<=m;i++)
  16.         scanf("%d", &L[i]);
  17.     for(int i=1;i<=k;i++)
  18.         scanf("%d", &P[i]);
  19.  
  20.     L[m+1] = n;
  21.     m ++;
  22.     dp[0][0] = 0;
  23.     for(int i=1;i<=m;i++) {
  24.         dp[i][1] = L[i] * P[1];
  25.     }
  26.     for(int p=2;p<=k;p++){
  27.         dp[0][p%2] = -INF;
  28.         int mx = -INF, idx;
  29.         mx = dp[p-1][(p-1)%2] - L[p-1]*P[p];
  30.         idx = p-1;
  31.         for(int i=p;i<=m;i++) {
  32.             dp[i][p%2] = (mx + L[idx]*P[p]) + P[p] * (L[i] - L[idx]);
  33.             if(dp[i][(p-1)%2] - L[i]*P[p] > mx){
  34.                 mx = dp[i][(p-1)%2] - L[i]*P[p];
  35.                 idx = i;
  36.             }
  37.         }
  38.     }
  39.  
  40.     printf("%d", dp[m][k%2]);
  41.     return 0;
  42. }
Advertisement
RAW Paste Data Copied
Advertisement