Submission #579050

#	Time	Username	Problem	Language	Result	Execution time	Memory
579050		Lucpp	Two Dishes (JOI19_dishes)	C++17	15 / 100	516 ms	32796 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 2e5;

ll a[2][MAX], t[2][MAX], p[2][MAX];

vector<vector<ll>> dp;
vector<vector<bool>> vis;
ll calc(int i, int j, ll tim){
    if(vis[i][j]) return dp[i][j];
    vis[i][j] = true;
    dp[i][j] = -INF;
    if(i > 0) dp[i][j] = max(dp[i][j], calc(i-1, j, tim-a[0][i-1]) + p[0][i-1]*(tim<=t[0][i-1]));
    if(j > 0) dp[i][j] = max(dp[i][j], calc(i, j-1, tim-a[1][j-1]) + p[1][j-1]*(tim<=t[1][j-1]));
    return dp[i][j];
}

int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < (i==0?n:m); j++)
            cin >> a[i][j] >> t[i][j] >> p[i][j];
    if(n <= 2000 && m <= 2000){
        dp.assign(n+1, vector<ll>(m+1));
        vis.assign(n+1, vector<bool>(m+1));
        vis[0][0] = true;
        ll tim = 0;
        for(int i = 0; i < n; ++i) tim += a[0][i];
        for(int i = 0; i < m; ++i) tim += a[1][i];
        cout << calc(n, m, tim) << "\n";
    }
    else{
        ll ans = -INF;
        ll points = 0;
        ll tim = 0;
        ll T = t[0][0];
        int i = 0, j = 0;
        for(; i < n; i++){
            if(tim + a[0][i] > T) break;
            tim += a[0][i];
            points += p[0][i];
        }
        for(; i >= 0; i--){
            for(; j < m; j++){
                if(tim + a[1][j] > T) break;
                tim += a[1][j];
                points += p[1][j];
            }
            ans = max(ans, points);
            if(i != 0){
                tim -= a[0][i-1];
                points -= p[0][i-1];
            }
        }
        cout << ans << "\n";
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9