Submission #1171108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171108		niepamietamhasla	Two Dishes (JOI19_dishes)	C++20	3 / 100	1 ms	400 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e3 + 5;

ll c1[MAXN];
ll c2[MAXN];
ll t1[MAXN];
ll t2[MAXN];
ll p1[MAXN];
ll p2[MAXN];

ll pref1[MAXN];
ll pref2[MAXN];

const ll INF = -1e18;

ll dp[MAXN][MAXN];

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int a, b, c;
    for(int i = 1; i <= n; ++i){
        cin >> c1[i] >> t1[i] >> p1[i];
    }
    for(int i = 1; i <= m; ++i){
        cin >> c2[i] >> t2[i] >> p2[i];
    }
    for(int i = 1; i <= n; ++i){
        pref1[i] = pref1[i - 1] + c1[i];
    }
    for(int i = 1; i <= m; ++i){
        pref2[i] = pref2[i - 1] + c2[i];
    }
    for(int i = 1; i <= n; ++i){
        dp[i][0] = dp[i-1][0] + (pref1[i] <= t1[i] ? p1[i] : 0);
    }
    for(int i = 1; i <= m; ++i){
        dp[0][i] = dp[0][i-1] + (pref2[i] <= t2[i] ? p2[i] : 0);
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            ll k1 = -INF;
            if(pref1[i-1] + pref2[j] + c1[i] <= t1[i]){
                k1 = dp[i-1][j] + p1[i];
            }
            else{
                k1 = dp[i-1][j];
            }
            ll k2 = -INF;
            if(pref1[i] + pref2[j-1] + c2[j] <= t2[j]){
                k2 = dp[i][j-1] + p2[j];
            }
            else{
                k2 = dp[i][j-1];
            }
            dp[i][j] = max(k1, k2);
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}

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