Submission #1073012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073012		NeroZein	Tricks of the Trade (CEOI23_trade)	C++17	100 / 100	3724 ms	45544 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 g[N];
int lx[N];
int cl, cr;
bool ok[N];
int pre[N];
long long s2; 
int c[N], s[N];
long long dp[N];
long long pref[N]; 
multiset<int> se, se2;
vector<int> to_add[N], to_rem[N];

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--);
}

long long solve(int l, int r, int optl, int optr) {
  if (l > r) {
    return -LLONG_MAX;
  }
  int mid = (l + r) >> 1;
  long long ret = -LLONG_MAX;
  int opt = -1; 
  for (int i = min(mid, optr); i >= optl; --i) {
    edit(i, mid);
    if ((int) se2.size() == k) {
      long long val = pref[mid] - pref[i - 1] + s2;
      if (val > ret) {
        ret = val;
        opt = i;
        lx[mid] = i;
      }
    }
  }
  dp[mid] = ret;
  ret = max(ret, solve(l, mid - 1, optl, opt));
  ret = max(ret, solve(mid + 1, r, opt, optr));
  return ret; 
}

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];
  }
  for (int i = 0; i < k; ++i) {
    dp[i] = -LLONG_MAX;
  }
  cl = 1, cr = 0;
  long long ans = solve(k, n, 1, n);
  int lst = -1; 
  for (int i = 1; i <= n; ++i) {
    if (lst != -1) {
      pre[i] = lx[lst];
    } else {
      pre[i] = 1; 
    }
    if (dp[i] == ans) {
      lst = i;
    }
  }
  for (int i = n, j = n; i >= 1; --i) {
    if (dp[i] != ans) {
      continue; 
    }
    if (j > i) {
      j = i;
    }
    while (j >= pre[i]) {
      edit(j, i);
      if (pref[i] - pref[j - 1] + s2 == ans && (int) se2.size() == k) {
        int mn = *se2.begin();
        to_add[j].push_back(mn);
        to_rem[i].push_back(mn);
      }
      if (j > pre[i]) {
        j--;        
      } else {
        break; 
      }
    }
  }
  multiset<int> ss;
  for (int i = 1; i <= n; ++i) {
    for (int j : to_add[i]) {
      ss.insert(j);
    }
    if (!ss.empty() && *ss.begin() <= s[i]) {
      ok[i] = true;
    }
    for (int j : to_rem[i]) {
      ss.erase(ss.find(j));
    }
  }
  cout << ans << '\n';
  for (int i = 1; i <= n; ++i) {
    cout << ok[i];
  }
  return 0;
}

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