Submission #1209233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209233		damamila	Tricks of the Trade (CEOI23_trade)	C++20	55 / 100	952 ms	2162688 KiB

trade

// Source: https://usaco.guide/general/io

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

#define int long long

signed main() {
    int n, k;
    cin >> n >> k;
    vector<int> c(n+1);
    vector<int> s(n+1);
    vector<vector<int>> dp(n+1, vector<int> (k+1, -1e18));
    vector<vector<int>> dpinv(n+2, vector<int> (k+1, -1e18));
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    // for (int i = 0; i <= k; i++) {
    //     dp[0][i] = 0;
    // }
    for (int i = 0; i <= n+1; i++) {
        dpinv[i][0] = 0;
    }
    // for (int i = 0; i <= k; i++) {
    //     dpinv[0][i] = 0;
    // }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = max(dp[i-1][j]-c[i], dp[i-1][j-1]-c[i]+s[i]);
            //cout << dp[i][j] << " - ";
        }
        //cout << endl;
    }
    //cout << "STOP" << endl;
    for (int i = n; i > 0; i--) {
        for (int j = 1; j <= k; j++) {
            dpinv[i][j] = max(dpinv[i+1][j]-c[i], dpinv[i+1][j-1]-c[i]+s[i]);
            //cout << i << " " << j << ": " << dpinv[i][j] << endl;
        }
        //cout << endl;
    }
    int ans = -1e18, ans2 = -1e18;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i][k]);
        ans2 = max(ans2, dpinv[i][k]);
    }
    cout << ans << endl;
    vector<bool> res(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            //cout << i << ": " << dp[i-1][j-1] << " " << dpinv[i+1][k-j] << endl;
            if (dp[i-1][j-1]+dpinv[i+1][k-j]+s[i]-c[i] == ans) res[i] = 1;
        }
        //cout << endl;
    }
    for (int i = 1; i <= n; i++) cout << res[i];
}









    

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 45