PROG-T1148: Sushi

#include <iostream>
#include <vector>
using namespace std;

using lli = long long;

int main(){

    int len, nct, npp;
    scanf("%d", &len);
    scanf("%d", &nct);
    scanf("%d", &npp);

    vector<int> cut(nct + 1, 0);
    for(int i = 1; i <= nct; ++i){
        scanf("%d", &cut[i]);
    }
    cut.push_back(len);
    ++nct;

    vector<int> like(npp + 1, 0);
    for(int i = 1; i <= npp; ++i){
        scanf("%d", &like[i]);
    }

    vector<vector<lli>> dp(2, vector<lli>(nct + 1, 0));
    for(int i = 1; i <= npp; ++i){
        int curr = i % 2;
        int prev = curr ^ 1;
        lli mx = -1e18;
        for(int j = i; nct - j >= npp - i; ++j){
            mx = max(mx, dp[prev][j - 1] - like[i] * cut[j - 1]);
            dp[curr][j] = mx + like[i] * cut[j];
        }
    }

    cout << dp[npp % 2][nct];

    return 0;
}