Submission #1060764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060764		MilosMilutinovic	Tricks of the Trade (CEOI23_trade)	C++14	10 / 100	8077 ms	4512 KiB

trade

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  vector<int> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  const long long inf = (long long) -1e18;
  long long res = inf;
  auto Calc = [&](int l, int r) {
    if (r - l + 1 < k) {
      return inf;
    }
    vector<int> v;
    long long ret = 0;
    for (int i = l; i <= r; i++) {
      ret -= c[i];
      v.push_back(s[i]);
    }
    sort(v.rbegin(), v.rend());
    for (int i = 0; i < min(k, (int) v.size()); i++) {
      ret += v[i];
    }
    return ret;
  };
  function<void(int, int, int, int)> Solve = [&](int l, int r, int optl, int optr) {
    if (l > r) {
      return;
    }
    int mid = (l + r) >> 1;
    int opt = min(optl, mid);
    long long best = Calc(opt, mid);
    for (int i = optl; i <= min(mid, optr); i++) {
      long long v = Calc(i, mid);
      if (v > best) {
        best = v;
        opt = i;
      }
    }
    res = max(res, best);
    Solve(l, mid - 1, optl, opt);
    Solve(mid + 1, r, opt, optr);
  };
  Solve(0, n - 1, 0, n - 1);
  cout << res << '\n';
  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