Submission #1208830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208830		anonymous321	Tricks of the Trade (CEOI23_trade)	C++20	25 / 100	1102 ms	2162688 KiB

trade

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = numeric_limits<ll>::max()/4;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> vc (n);
    for (int i = 0; i < n; i++) {
        cin >> vc[i];
    }
    vector<ll> vs (n);
    for (int i = 0; i < n; i++) {
        cin >> vs[i];
    }
    
    vector<ll> p (n+1, 0);
    for (int i = 0; i < n; i++) {
        p[i+1] = p[i] - vc[i];
    }
    
    vector<vector<ll>> dp (k, vector<ll> (n, -INF));
    vector<vector<int>> dp_p (k, vector<int> (n, -1));
    for (int i = 0; i < n; i++) {
        dp[0][i] = vs[i] - vc[i];
    }
    for (int i = 1; i < k; i++) {
        ll mval = -INF;
        int mid = -1;
        for (int j = 0; j < n; j++) {
            dp[i][j] = mval + p[j+1] + vs[j];
            dp_p[i][j] = mid;
            ll x = dp[i - 1][j] - p[j+1];
            if (mval < x) {
                mval = x;
                mid = j;
            }
        }
    }

    vector<ll> maxval (k, -INF);
    vector<bool> sol (n, false);
    vector<vector<bool>> poss (k, vector<bool> (n, false));
    ll sm = *max_element(dp[k-1].begin(), dp[k-1].end());
    for (int i = 0; i < n; i++) {
        if (dp[k-1][i] == sm) {
            poss[k-1][i] = true;
            sol[i] = true;
        }
    }
    
    for (int i = k-1; i > 0; i--) {
        vector<tuple<int, int, ll>> vq {};
        for (int j = 0; j < n; j++) {
            if (poss[i][j]) {
                vq.push_back({dp_p[i][j], j, dp[i-1][dp_p[i][j]]});
            }
        }
        int cur = 0;
        for (int j = 0; j < n; j++) {
            if (cur == vq.size()) break;
            while (cur < vq.size() && j >= get<1>(vq[cur])) {
                cur++;
            }
            if (cur == vq.size()) break;
            if (j >= get<0>(vq[cur]) && j < get<1>(vq[cur]) && dp[i-1][j] == get<2>(vq[cur])) {
                poss[i-1][j] = true;
                sol[j] = true;
            }
        }
    }

    cout << *max_element(dp[k-1].begin(), dp[k-1].end()) << "\n";
    for (int i = 0; i < n; i++) {
        if (sol[i]) cout << 1;
        else cout << 0;
    }
    cout << "\n";
    return 0;
}

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