Submission #1224576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224576		LaMatematica14	Tricks of the Trade (CEOI23_trade)	C++20	10 / 100	8087 ms	5100 KiB

trade

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

int main() {
    int N, K; cin >> N >> K;
    vector<long long> T(N), S(N);
    for (int i = 0; i < N; i++) cin >> T[i];
    for (int i = 0; i < N; i++) cin >> S[i];
    //for (int i = 0; i < N; i++) S[i] -= T[i];
    
    long long best = -1e14;
    vector<int> belli(N, 0);
    for (int i = 0; i < N; i++) {
        priority_queue<int> pq;
        long long att = 0;
        for (int j = i; j < N; j++) {
            att += S[j]-T[j];
            pq.push(-S[j]);
            if (pq.size() > K) {
                att += pq.top();
                pq.pop();  
            }
            if (pq.size() == K) best = max(best, att);
        }
    }
    for (int i = 0; i < N; i++) {
        priority_queue<pair<int, int>> pq;
        long long att = 0;
        int lb = -1;
        for (int j = i; j < N; j++) {
            att += S[j]-T[j];
            pq.push({-S[j], j});
            if (pq.size() > K) {
                att += pq.top().first;
                if (pq.top().second <= lb) belli[pq.top().second] = 1;
                pq.pop();  
            }
            if ((pq.size() == K) && att == best) lb = j;
        }
        while (!pq.empty()) {
            if (pq.top().second <= lb) belli[pq.top().second] = 1;
            pq.pop();
        }
    }
    cout << best << endl;
    for (int i = 0; i < N; i++) cout << belli[i];
    cout << endl;
}

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