# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
330815 |
2020-11-26T16:19:57 Z |
two_sides |
Feast (NOI19_feast) |
C++17 |
|
308 ms |
17552 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct block {
ll val;
block *prev, *next;
block(ll val): val(val) {
prev = next = nullptr;
}
};
using blockpt = block*;
struct compare {
bool operator () (const blockpt x,
const blockpt &y) const {
return abs(x->val) != abs(y->val) ?
abs(x->val) < abs(y->val) : x < y;
}
};
const int N = 3e5 + 5;
set <block*, compare> blocks;
int a[N]; block *b[N];
bool sign(const int &x) {
return x <= 0 ? 0 : 1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k, m = 0, p = 0;
cin >> n >> k;
for (int i = 1; i <= n; cin >> a[i++]);
for (int i = 1; i <= n; ) {
int j = i; ll sum = 0;
while (j <= n && sign(a[i])
== sign(a[j])) sum += a[j++];
if (sum > 0 || m) {
b[m++] = new block(sum);
blocks.insert(b[m - 1]);
}
i = j; p += sum > 0;
}
for (int i = 1; i < m; i++) {
b[i]->prev = b[i - 1];
b[i - 1]->next = b[i];
}
while (p > k && blocks.size()) {
blockpt it = *blocks.begin();
blocks.erase(it);
if (it->val > 0) p--;
if (it->prev) {
blocks.erase(it->prev);
if (it->prev->val > 0) p--;
it->val += it->prev->val;
it->prev = it->prev->prev;
if (it->prev)
it->prev->next = it;
}
if (it->next) {
blocks.erase(it->next);
if (it->next->val > 0) p--;
it->val += it->next->val;
it->next = it->next->next;
if (it->next)
it->next->prev = it;
}
if (it->val > 0 ||
(it->prev && it->next)) {
if (it->val > 0) p++;
blocks.insert(it);
}
else it->val = 0;
}
ll res = 0;
for (auto it : blocks)
res += max(0ll, it->val);
cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
1516 KB |
Output is correct |
2 |
Correct |
34 ms |
1516 KB |
Output is correct |
3 |
Correct |
34 ms |
1516 KB |
Output is correct |
4 |
Correct |
34 ms |
1644 KB |
Output is correct |
5 |
Correct |
34 ms |
1516 KB |
Output is correct |
6 |
Correct |
33 ms |
1516 KB |
Output is correct |
7 |
Correct |
33 ms |
1516 KB |
Output is correct |
8 |
Correct |
34 ms |
1516 KB |
Output is correct |
9 |
Correct |
33 ms |
1516 KB |
Output is correct |
10 |
Correct |
33 ms |
1516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
1516 KB |
Output is correct |
2 |
Correct |
24 ms |
2668 KB |
Output is correct |
3 |
Correct |
25 ms |
2668 KB |
Output is correct |
4 |
Correct |
25 ms |
2668 KB |
Output is correct |
5 |
Correct |
34 ms |
3308 KB |
Output is correct |
6 |
Correct |
23 ms |
2668 KB |
Output is correct |
7 |
Correct |
24 ms |
2668 KB |
Output is correct |
8 |
Correct |
35 ms |
3308 KB |
Output is correct |
9 |
Correct |
34 ms |
3308 KB |
Output is correct |
10 |
Correct |
24 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
292 ms |
14188 KB |
Output is correct |
2 |
Correct |
285 ms |
17004 KB |
Output is correct |
3 |
Correct |
308 ms |
17260 KB |
Output is correct |
4 |
Correct |
279 ms |
17132 KB |
Output is correct |
5 |
Correct |
289 ms |
17132 KB |
Output is correct |
6 |
Correct |
284 ms |
17260 KB |
Output is correct |
7 |
Correct |
292 ms |
17388 KB |
Output is correct |
8 |
Correct |
283 ms |
17388 KB |
Output is correct |
9 |
Correct |
307 ms |
17388 KB |
Output is correct |
10 |
Correct |
289 ms |
17552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
1516 KB |
Output is correct |
2 |
Correct |
34 ms |
1516 KB |
Output is correct |
3 |
Correct |
34 ms |
1516 KB |
Output is correct |
4 |
Correct |
34 ms |
1644 KB |
Output is correct |
5 |
Correct |
34 ms |
1516 KB |
Output is correct |
6 |
Correct |
33 ms |
1516 KB |
Output is correct |
7 |
Correct |
33 ms |
1516 KB |
Output is correct |
8 |
Correct |
34 ms |
1516 KB |
Output is correct |
9 |
Correct |
33 ms |
1516 KB |
Output is correct |
10 |
Correct |
33 ms |
1516 KB |
Output is correct |
11 |
Correct |
23 ms |
1516 KB |
Output is correct |
12 |
Correct |
24 ms |
2668 KB |
Output is correct |
13 |
Correct |
25 ms |
2668 KB |
Output is correct |
14 |
Correct |
25 ms |
2668 KB |
Output is correct |
15 |
Correct |
34 ms |
3308 KB |
Output is correct |
16 |
Correct |
23 ms |
2668 KB |
Output is correct |
17 |
Correct |
24 ms |
2668 KB |
Output is correct |
18 |
Correct |
35 ms |
3308 KB |
Output is correct |
19 |
Correct |
34 ms |
3308 KB |
Output is correct |
20 |
Correct |
24 ms |
2668 KB |
Output is correct |
21 |
Correct |
292 ms |
14188 KB |
Output is correct |
22 |
Correct |
285 ms |
17004 KB |
Output is correct |
23 |
Correct |
308 ms |
17260 KB |
Output is correct |
24 |
Correct |
279 ms |
17132 KB |
Output is correct |
25 |
Correct |
289 ms |
17132 KB |
Output is correct |
26 |
Correct |
284 ms |
17260 KB |
Output is correct |
27 |
Correct |
292 ms |
17388 KB |
Output is correct |
28 |
Correct |
283 ms |
17388 KB |
Output is correct |
29 |
Correct |
307 ms |
17388 KB |
Output is correct |
30 |
Correct |
289 ms |
17552 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
36 |
Halted |
0 ms |
0 KB |
- |