제출 #1288070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288070		LIA	Tricks of the Trade (CEOI23_trade)	C++17	5 / 100	76 ms	22284 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 pre(n);
  set<pll, greater<pll>> wind;
  for (ll i = 0; i < n; ++i) {
    pre[i] = (i == 0 ? 0 : pre[i - 1]) + b[i];
    if (!wind.empty()) {
      ll my_ans = s[i] - pre[i] + wind.begin()->first;
      ans = max(ans, my_ans);
    }
    wind.insert({(i == 0 ? 0 : pre[i - 1]) + s[i], i});
  }

  // vll in(n), res(n);
  // 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;
  //         res = in;
  //       }
  //     }
  //   }
  // }

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

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

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