제출 #1209173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209173		kirakaminski968	Tricks of the Trade (CEOI23_trade)	C++20	0 / 100	0 ms	324 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 <= 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] = 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] = 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]);
    }
    if (ans != ans2) return 1;
    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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45