Advertisement

# PROG-1148: Sushi

Mar 29th, 2021 (edited)
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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