Submission #1288061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288061		LIA	Tricks of the Trade (CEOI23_trade)	C++17	5 / 100	8090 ms	8196 KiB

trade

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  ll n, k, ans = -1e18;
  cin >> n >> k;
  vll b(n), s(n);
  for (ll i = 0; i < n; ++i)
    cin >> b[i];
  for (ll i = 0; i < n; ++i)
    cin >> s[i];

  vll in(n), res(n);
  ll tag = 0;
  for (ll st = 0; st < n; ++st) {
    ll sum_buy = 0;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    ll sum_pq = 0;
    in.assign(n, 0);
    for (ll ed = st; ed < n; ++ed) {
      sum_buy += b[ed];
      pq.push({s[ed], ed});
      in[ed] = 1;
      sum_pq += s[ed];
      while (pq.size() > k) {
        auto [node, idx] = pq.top();
        pq.pop();
        sum_pq -= node;
        in[idx] = 0;
      }
      if (pq.size() == k) {
        ll ans_ed = sum_pq - sum_buy;
        if (ans < ans_ed) {
          ans = ans_ed;
          ++tag;
          auto pq2 = pq;
          while (!pq2.empty()) {
            ll idx = pq2.top().second;
            pq2.pop();
            res[idx] = tag;
          }
        } else if (ans == ans_ed) {
          auto pq2 = pq;
          while (!pq2.empty()) {
            ll idx = pq2.top().second;
            pq2.pop();
            res[idx] = tag;
          }
        }
      }
    }
  }

  cout << ans << endl;
  string ss(n, '0');

  for (ll i = 0; i < n; ++i)
    if (res[i] == tag)
      ss[i] = '1';
  cout << ss << endl;
  return 0;
}

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