제출 #1288052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288052		LIA	Tricks of the Trade (CEOI23_trade)	C++17	5 / 100	8092 ms	4160 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];

  set<ll> in;
  set<ll> res;
  for (ll st = 0; st < n; ++st) {
    ll sum_buy = 0;
    priority_queue<pll, vector<pll>, greater<pll>> pq;
    ll sum_pq = 0;
    in.clear();
    for (ll ed = st; ed < n; ++ed) {
      sum_buy += b[ed];
      pq.push({s[ed], ed});
      in.insert(ed);
      sum_pq += s[ed];
      while (pq.size() > k) {
        auto [node, idx] = pq.top();
        pq.pop();
        sum_pq -= node;
        in.erase(in.find(idx));
      }
      if (pq.size() == k) {
        ll ans_ed = sum_pq - sum_buy;
        if (ans < ans_ed) {
          ans = ans_ed;
          res = in;
        }
      }
    }
  }

  cout << ans << endl;
  string ss(n, '0');
  for (auto it : res)
    ss[it] = '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