oj.uz

Submission #1072406

# Submission time Handle Problem Language Result Execution time Memory
1072406 2024-08-23T18:32:58 Z NeroZein Tricks of the Trade (CEOI23_trade) C++17
10 / 100
 8000 ms 16980 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--);
  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 / 0.0

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

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 4 ms 344 KB Partially correct
5 Partially correct 3 ms 348 KB Partially correct
6 Partially correct 3 ms 348 KB Partially correct
7 Partially correct 4 ms 492 KB Partially correct
8 Partially correct 3 ms 348 KB Partially correct
9 Partially correct 3 ms 348 KB Partially correct
10 Partially correct 4 ms 348 KB Partially correct
11 Partially correct 3 ms 348 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 344 KB Partially correct
2 Partially correct 0 ms 348 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 4 ms 344 KB Partially correct
5 Partially correct 3 ms 348 KB Partially correct
6 Partially correct 3 ms 348 KB Partially correct
7 Partially correct 4 ms 492 KB Partially correct
8 Partially correct 3 ms 348 KB Partially correct
9 Partially correct 3 ms 348 KB Partially correct
10 Partially correct 4 ms 348 KB Partially correct
11 Partially correct 3 ms 348 KB Partially correct
12 Partially correct 0 ms 348 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 5 ms 348 KB Partially correct
16 Partially correct 3 ms 348 KB Partially correct
17 Partially correct 3 ms 348 KB Partially correct
18 Partially correct 4 ms 348 KB Partially correct
19 Partially correct 3 ms 348 KB Partially correct
20 Partially correct 3 ms 348 KB Partially correct
21 Partially correct 3 ms 348 KB Partially correct
22 Partially correct 3 ms 348 KB Partially correct
23 Partially correct 3683 ms 916 KB Partially correct
24 Partially correct 2671 ms 900 KB Partially correct
25 Partially correct 4745 ms 888 KB Partially correct
26 Partially correct 4112 ms 888 KB Partially correct
27 Partially correct 2967 ms 856 KB Partially correct
28 Partially correct 3274 ms 856 KB Partially correct
29 Partially correct 4954 ms 896 KB Partially correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Execution timed out 8052 ms 16980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Execution timed out 8052 ms 16980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 1 ms 504 KB Partially correct
3 Partially correct 1 ms 344 KB Partially correct
4 Partially correct 0 ms 348 KB Partially correct
5 Partially correct 1 ms 348 KB Partially correct
6 Partially correct 4 ms 344 KB Partially correct
7 Partially correct 3 ms 348 KB Partially correct
8 Partially correct 3 ms 348 KB Partially correct
9 Partially correct 4 ms 492 KB Partially correct
10 Partially correct 3 ms 348 KB Partially correct
11 Partially correct 3 ms 348 KB Partially correct
12 Partially correct 4 ms 348 KB Partially correct
13 Partially correct 3 ms 348 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 0 ms 348 KB Partially correct
16 Partially correct 0 ms 348 KB Partially correct
17 Partially correct 5 ms 348 KB Partially correct
18 Partially correct 3 ms 348 KB Partially correct
19 Partially correct 3 ms 348 KB Partially correct
20 Partially correct 4 ms 348 KB Partially correct
21 Partially correct 3 ms 348 KB Partially correct
22 Partially correct 3 ms 348 KB Partially correct
23 Partially correct 3 ms 348 KB Partially correct
24 Partially correct 3 ms 348 KB Partially correct
25 Partially correct 3683 ms 916 KB Partially correct
26 Partially correct 2671 ms 900 KB Partially correct
27 Partially correct 4745 ms 888 KB Partially correct
28 Partially correct 4112 ms 888 KB Partially correct
29 Partially correct 2967 ms 856 KB Partially correct
30 Partially correct 3274 ms 856 KB Partially correct
31 Partially correct 4954 ms 896 KB Partially correct
32 Partially correct 1 ms 348 KB Partially correct
33 Execution timed out 8052 ms 16980 KB Time limit exceeded
34 Halted 0 ms 0 KB -