Submission #1289104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289104		LIA	Tricks of the Trade (CEOI23_trade)	C++17	10 / 100	8093 ms	6312 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>
const ll inf = 1e18;

ll ans = -inf;
ll n, k;
vll b, s;
vll pre;
void dc(ll l, ll r, ll optl, ll optr) {
  if (l > r)
    return;
  ll mid = (l + r) / 2;

  ll ans_mid = -inf, opt = optr;
  ll st = max(optl, mid), ed = optr;
  if (st > ed) {
    dc(l, mid - 1, optl, optl);
    dc(mid + 1, r, optl, optr);
    return;
  }

  priority_queue<ll, vll, greater<ll>> pq;
  ll sum_k_best = 0;

  for (ll t = mid; t < st; ++t) {
    pq.push(s[t]);
    sum_k_best += s[t];
    if (pq.size() > k) {
      sum_k_best -= pq.top();
      pq.pop();
    }
  }

  for (ll i = st; i <= ed; ++i) {
    pq.push(s[i]);
    sum_k_best += s[i];
    if (pq.size() > k) {
      sum_k_best -= pq.top();
      pq.pop();
    }
    ll len = i - mid + 1;
    if (len < k)
      continue;
    ll sum_costs = pre[i] - (mid == 0 ? 0 : pre[mid - 1]);
    ll cur = sum_k_best - sum_costs;
    if (cur > ans_mid) {
      ans_mid = cur;
      opt = i;
    }
  }

  ans = max(ans, ans_mid);
  dc(l, mid - 1, optl, opt);
  dc(mid + 1, r, opt, optr);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n >> k;
  b.resize(n);
  s.resize(n);
  pre.resize(n);

  for (ll i = 0; i < n; ++i) {
    cin >> b[i];
    pre[i] = (i == 0 ? 0 : pre[i - 1]) + b[i];
  }
  for (ll i = 0; i < n; ++i)
    cin >> s[i];

  dc(0, n - 1, 0, n - 1);

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

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