Submission #1288177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288177		LIA	Tricks of the Trade (CEOI23_trade)	C++17	20 / 100	8087 ms	275960 KiB

trade

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define vll vector<ll>
#define pll pair<ll, ll>
#define tp tuple<ll, 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];
  vector<tp> vec;
  for (ll st = 0; st < n; ++st) {
    ll sum_buy = 0;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    ll sum_pq = 0;
    for (ll ed = st; ed < n; ++ed) {
      sum_buy += b[ed];
      pq.push({s[ed], ed});
      sum_pq += s[ed];
      while (pq.size() > k) {
        auto [node, idx] = pq.top();
        pq.pop();
        sum_pq -= node;
      }
      if (pq.size() == k) {
        ll ans_ed = sum_pq - sum_buy;
        if (ans < ans_ed) {
          vec.clear();
          ll t = pq.top().first;
          ans = ans_ed;
          vec.push_back({st, ed, t});
        } else if (ans == ans_ed) {
          ans = ans_ed;
          ll t = pq.top().first;
          vec.push_back({st, ed, t});
        }
      }
    }
  }

  multiset<ll> k_in;
  string ansi(n, '0');

  vector<vector<pll>> updates(n + 1);

  for (auto [l, r, c] : vec) {
    updates[l].push_back({c, 1});
    updates[r + 1].push_back({c, -1});
  }

  for (ll i = 0; i < n; ++i) {
    for (auto [c, t] : updates[i]) {
      if (t == 1) {
        k_in.insert(c);
      } else {
        auto it = k_in.find(c);
        if (it != k_in.end())
          k_in.erase(it);
      }
    }

    if (!k_in.empty()) {     
      ll mn = *k_in.begin(); 
      if (s[i] >= mn)
        ansi[i] = '1';
    }
  }

  cout << ans << endl
       << ansi;
  return 0;
}

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