# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
638365 |
2022-09-05T16:08:39 Z |
shmad |
Feast (NOI19_feast) |
C++17 |
|
209 ms |
15548 KB |
#include <bits/stdc++.h>
#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'
#define bit(x, i) ((x) >> (i) & 1)
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using vvt = vt< vt<int> >;
const int N = 1e6 + 5, mod = 1e9 + 7, B = 500;
const ll inf = 1e18 + 7, LIM = (1ll << 60);
const double eps = 1e-6;
int n, k;
ll l[N], r[N];
ll a[N], b[N];
void solve () {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
int m = 0;
for (int i = 1; i <= n; i++) {
if (m == 0) {
if (a[i] > 0) b[++m] = a[i];
continue;
}
if ((a[i] > 0 && b[m] > 0) || (a[i] < 0 && b[m] < 0)) b[m] += a[i];
else b[++m] = a[i];
}
if (b[m] < 0) b[m--] = 0;
set<pii> s;
int cnt = 0;
for (int i = 1; i <= m; i++) {
s.insert({abs(b[i]), i});
l[i] = i - 1;
r[i] = i + 1;
cnt += (b[i] > 0);
}
while (cnt > k) {
pii v = *s.begin();
s.erase(s.begin());
ll i = v.ss;
if (b[i] > 0) cnt--;
if (l[i] != 0) {
if (b[l[i]] > 0) cnt--;
s.erase({abs(b[l[i]]), l[i]});
b[i] += b[l[i]];
if (l[l[i]] != 0) r[l[l[i]]] = i;
}
if (r[i] != m + 1) {
if (b[r[i]] > 0) cnt--;
s.erase({abs(b[r[i]]), r[i]});
b[i] += b[r[i]];
if (r[r[i]] != m + 1) l[r[r[i]]] = i;
}
b[l[i]] = b[r[i]] = 0;
l[i] = l[l[i]];
r[i] = r[r[i]];
if (b[i] < 0) {
if (l[i] == 0) l[r[i]] = b[i] = 0;
if (l[i] != 0 && r[i] == m + 1) r[l[i]] = m + 1, b[i] = 0;
}
s.insert({abs(b[i]), i});
cnt += (b[i] > 0);
}
ll ans = 0;
for (auto [val, i]: s) if (b[i] > 0) ans += b[i];
cout << ans;
cout << '\n';
}
bool testcases = 0;
signed main() {
#ifdef ONLINE_JUDGE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
cin.tie(0) -> sync_with_stdio(0);
int test = 1;
if (testcases) cin >> test;
for (int cs = 1; cs <= test; cs++) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
2516 KB |
Output is correct |
2 |
Correct |
29 ms |
2628 KB |
Output is correct |
3 |
Correct |
37 ms |
2648 KB |
Output is correct |
4 |
Correct |
29 ms |
2568 KB |
Output is correct |
5 |
Correct |
31 ms |
2700 KB |
Output is correct |
6 |
Correct |
29 ms |
2492 KB |
Output is correct |
7 |
Correct |
26 ms |
2532 KB |
Output is correct |
8 |
Correct |
28 ms |
2572 KB |
Output is correct |
9 |
Correct |
33 ms |
2604 KB |
Output is correct |
10 |
Correct |
28 ms |
2664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
2628 KB |
Output is correct |
2 |
Correct |
18 ms |
2660 KB |
Output is correct |
3 |
Correct |
23 ms |
2644 KB |
Output is correct |
4 |
Correct |
22 ms |
2656 KB |
Output is correct |
5 |
Correct |
27 ms |
2604 KB |
Output is correct |
6 |
Correct |
18 ms |
2636 KB |
Output is correct |
7 |
Correct |
19 ms |
2752 KB |
Output is correct |
8 |
Correct |
34 ms |
2668 KB |
Output is correct |
9 |
Correct |
28 ms |
2504 KB |
Output is correct |
10 |
Correct |
17 ms |
2688 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
195 ms |
15320 KB |
Output is correct |
2 |
Correct |
199 ms |
15132 KB |
Output is correct |
3 |
Correct |
208 ms |
15328 KB |
Output is correct |
4 |
Correct |
190 ms |
15056 KB |
Output is correct |
5 |
Correct |
199 ms |
15180 KB |
Output is correct |
6 |
Correct |
209 ms |
15420 KB |
Output is correct |
7 |
Correct |
209 ms |
15468 KB |
Output is correct |
8 |
Correct |
200 ms |
15300 KB |
Output is correct |
9 |
Correct |
195 ms |
15548 KB |
Output is correct |
10 |
Correct |
188 ms |
15508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
2516 KB |
Output is correct |
2 |
Correct |
29 ms |
2628 KB |
Output is correct |
3 |
Correct |
37 ms |
2648 KB |
Output is correct |
4 |
Correct |
29 ms |
2568 KB |
Output is correct |
5 |
Correct |
31 ms |
2700 KB |
Output is correct |
6 |
Correct |
29 ms |
2492 KB |
Output is correct |
7 |
Correct |
26 ms |
2532 KB |
Output is correct |
8 |
Correct |
28 ms |
2572 KB |
Output is correct |
9 |
Correct |
33 ms |
2604 KB |
Output is correct |
10 |
Correct |
28 ms |
2664 KB |
Output is correct |
11 |
Correct |
19 ms |
2628 KB |
Output is correct |
12 |
Correct |
18 ms |
2660 KB |
Output is correct |
13 |
Correct |
23 ms |
2644 KB |
Output is correct |
14 |
Correct |
22 ms |
2656 KB |
Output is correct |
15 |
Correct |
27 ms |
2604 KB |
Output is correct |
16 |
Correct |
18 ms |
2636 KB |
Output is correct |
17 |
Correct |
19 ms |
2752 KB |
Output is correct |
18 |
Correct |
34 ms |
2668 KB |
Output is correct |
19 |
Correct |
28 ms |
2504 KB |
Output is correct |
20 |
Correct |
17 ms |
2688 KB |
Output is correct |
21 |
Correct |
195 ms |
15320 KB |
Output is correct |
22 |
Correct |
199 ms |
15132 KB |
Output is correct |
23 |
Correct |
208 ms |
15328 KB |
Output is correct |
24 |
Correct |
190 ms |
15056 KB |
Output is correct |
25 |
Correct |
199 ms |
15180 KB |
Output is correct |
26 |
Correct |
209 ms |
15420 KB |
Output is correct |
27 |
Correct |
209 ms |
15468 KB |
Output is correct |
28 |
Correct |
200 ms |
15300 KB |
Output is correct |
29 |
Correct |
195 ms |
15548 KB |
Output is correct |
30 |
Correct |
188 ms |
15508 KB |
Output is correct |
31 |
Correct |
0 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
0 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
0 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
39 |
Halted |
0 ms |
0 KB |
- |