PROG-1148: Sushi

#include <bits/stdc++.h>

using namespace std;
const int INF = 2e9;
using pi = pair <int, int>;
int n, m, k;
int L[20010];
int P[20010];
vector < vector <int>> dp(20010, vector <int> (2, -INF));

int main(){

    scanf("%d%d%d", &n, &m, &k);

    for(int i=1;i<=m;i++)
        scanf("%d", &L[i]);
    for(int i=1;i<=k;i++)
        scanf("%d", &P[i]);

    L[m+1] = n;
    m ++;
    dp[0][0] = 0;
    for(int i=1;i<=m;i++) {
        dp[i][1] = L[i] * P[1];
    }
    for(int p=2;p<=k;p++){
        dp[0][p%2] = -INF;
        int mx = -INF, idx;
        mx = dp[p-1][(p-1)%2] - L[p-1]*P[p];
        idx = p-1;
        for(int i=p;i<=m;i++) {
            dp[i][p%2] = (mx + L[idx]*P[p]) + P[p] * (L[i] - L[idx]);
            if(dp[i][(p-1)%2] - L[i]*P[p] > mx){
                mx = dp[i][(p-1)%2] - L[i]*P[p];
                idx = i;
            }
        }
    }

    printf("%d", dp[m][k%2]);
    return 0;
}