Submission #579046

#	Time	Username	Problem	Language	Result	Execution time	Memory
579046		Lucpp	Two Dishes (JOI19_dishes)	C++17	10 / 100	482 ms	32852 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";
    }
}

• Subtask 1: 0 / 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