Submission #1072406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072406		NeroZein	Tricks of the Trade (CEOI23_trade)	C++17	10 / 100	8052 ms	16980 KiB

trade

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 250003;

int n, k;
int cl, cr;
long long s2; 
int c[N], s[N];
long long pref[N]; 
multiset<int> se, se2;

void balance() {
  if ((int) se2.size() > k) {
    int mn = *se2.begin();
    s2 -= mn;
    se.insert(mn); 
    se2.erase(se2.begin());
  }
  if ((int) se2.size() < k && !se.empty()) {
    int mx = *se.rbegin();
    s2 += mx; 
    se2.insert(mx); 
    se.erase(se.find(mx));
  }
}

void add(int ind) {
  se2.insert(s[ind]);
  s2 += s[ind];
  balance();
}

void rem(int ind) {
  if (se2.count(s[ind])) {
    s2 -= s[ind];
    se2.erase(se2.find(s[ind]));
  } else {
    se.erase(se.find(s[ind]));
  }
  balance(); 
}

void edit(int l, int r) {
  while (cl > l) add(--cl);
  while (cr < r) add(++cr);
  while (cl < l) rem(cl++);
  while (cr > r) rem(cr--);
  debug(l, r, cl, cr);
}

//void solve(int l, int r, int optl, int optr) {
  
//}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> c[i]; 
    pref[i] = pref[i - 1] - c[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> s[i];
  }
  long long ans = -LLONG_MAX;
  cl = 1, cr = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j <= n; ++j) {
      edit(i, j);
      long long p = pref[j];
      p -= pref[i - 1]; 
      if ((int) se2.size() == k) {
        ans = max(ans, s2 + p);
      }
    }
  }
  cout << ans << '\n'; 
  //solve(1, n, 1, 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