oj.uz

Submission #1072415

# Submission time Handle Problem Language Result Execution time Memory
1072415 2024-08-23T18:42:24 Z NeroZein Tricks of the Trade (CEOI23_trade) C++17
5 / 100
 2073 ms 18252 KB 
#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--);
}

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;
      }
    }
  }
  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];
  }
  cl = 1, cr = 0;
  cout << solve(1, n, 1, n) << '\n';
  return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 465 ms 9988 KB Partially correct
3 Partially correct 690 ms 13136 KB Partially correct
4 Partially correct 848 ms 13336 KB Partially correct
5 Partially correct 857 ms 13164 KB Partially correct
6 Partially correct 779 ms 12796 KB Partially correct
7 Partially correct 2008 ms 18252 KB Partially correct
8 Partially correct 741 ms 13260 KB Partially correct
9 Partially correct 671 ms 11684 KB Partially correct
10 Partially correct 729 ms 12316 KB Partially correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 465 ms 9988 KB Partially correct
3 Partially correct 690 ms 13136 KB Partially correct
4 Partially correct 848 ms 13336 KB Partially correct
5 Partially correct 857 ms 13164 KB Partially correct
6 Partially correct 779 ms 12796 KB Partially correct
7 Partially correct 2008 ms 18252 KB Partially correct
8 Partially correct 741 ms 13260 KB Partially correct
9 Partially correct 671 ms 11684 KB Partially correct
10 Partially correct 729 ms 12316 KB Partially correct
11 Partially correct 1 ms 344 KB Partially correct
12 Partially correct 457 ms 11108 KB Partially correct
13 Partially correct 705 ms 13136 KB Partially correct
14 Partially correct 825 ms 13332 KB Partially correct
15 Partially correct 835 ms 13144 KB Partially correct
16 Partially correct 781 ms 12624 KB Partially correct
17 Partially correct 2073 ms 18024 KB Partially correct
18 Partially correct 766 ms 13008 KB Partially correct
19 Partially correct 667 ms 11684 KB Partially correct
20 Partially correct 711 ms 12316 KB Partially correct
21 Partially correct 0 ms 348 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Incorrect 1 ms 464 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 600 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 0 ms 348 KB Partially correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -