Submission #1209128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209128		damamila	Tricks of the Trade (CEOI23_trade)	C++20	25 / 100	977 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));
    vector<vector<bool>> opt(n+1, vector<bool> (k+1, 0));
    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 <= n+1; i++) {
        dpinv[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = dp[i-1][j]-c[i];
            if (dp[i][j] < dp[i-1][j-1]-c[i]+s[i]) {
                opt[i][j] = 1;
                dp[i][j] = 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] = dpinv[i+1][j]-c[i];
            if (dpinv[i][j] < dpinv[i+1][j-1]-c[i]+s[i]) {
                dpinv[i][j] = dpinv[i+1][j-1]-c[i]+s[i];
            }
            //cout << i << " " << j << ": " << dpinv[i][j] << endl;
        }
        //cout << endl;
    }
    int ans = -1e18;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[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 << opt[i][j] << " " << dp[i][j] << " " << dpinv[i+1][k-j] << " " << c[i] << " " << s[i] << endl;
            if (opt[i][j] && dp[i][j]+dpinv[i+1][k-j] == ans) res[i] = 1;
        }
        //cout << endl;
    }
    for (int i = 1; i <= n; i++) cout << res[i];
}

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