# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
333071 |
2020-12-04T12:01:30 Z |
guka415 |
Feast (NOI19_feast) |
C++14 |
|
458 ms |
26724 KB |
#define _CRT_SECURE_NO_WARNINGS
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int sz = 3e5 + 5;
int k, n;
ll a[sz];
map<int, pair<ll, bool>> arr; //pos, val, isNeg
set<pair<ll, pair<bool, int>>> q;//val, pos, isNeg
inline pair<int, pair<ll, bool>> qToArr(pair<ll, pair<bool, int> > x) {
return { x.second.second, {x.first,x.second.first} };
}
inline pair<ll, pair<bool, int>> arrToQ(pair<int, pair<ll, bool>> x) {
return { x.second.first,{x.second.second,x.first} };
}
bool fix(vector<ll>& v) {
if (v.back() < 0)v.pop_back();
if (v.empty())return 0;
reverse(v.begin(), v.end());
if (v.back() < 0)v.pop_back();
if (v.empty())return 0;
return 1;
}
void removeFromDS(pair<ll, pair<bool, int>> x) {
auto y = arr.find(x.second.second), yp = y, ym = y;
yp++;
ym--;
if (x.second.first) {
ll nval = yp->second.first + ym->second.first - x.first;
q.erase(arrToQ(*yp));
q.erase(arrToQ(*ym));
q.erase(x);
q.insert({ nval,{0,x.second.second} });
arr[x.second.second] = { nval, 0 };
arr.erase(yp);
arr.erase(ym);
}
else {
if (ym == arr.end()) {
q.erase(arrToQ(*yp));
q.erase(x);
arr.erase(yp);
arr.erase(qToArr(x).first);
}
else if (yp == arr.end()) {
q.erase(arrToQ(*ym));
q.erase(x);
arr.erase(ym);
arr.erase(qToArr(x).first);
}
else {
ll nval = yp->second.first + ym->second.first - x.first;
q.erase(arrToQ(*yp));
q.erase(arrToQ(*ym));
q.erase(x);
q.insert({ nval,{1,x.second.second} });
arr[x.second.second] = { nval, 1 };
arr.erase(yp);
arr.erase(ym);
}
}
}
ll solve(vector<ll> v) {
if (!fix(v))return 0;
ll tot = 0;
int vsz = v.size();
for (int i = 0; i < vsz; i += 2) {
tot += v[i];
}
foru(i, 0, vsz) {
arr[i] = { abs(v[i]),i & 1 }; q.insert({ abs(v[i]),{i & 1,i} });
}
int cur = vsz / 2 + 1;
while (cur > k) {
auto x = *q.begin();
tot -= x.first;
removeFromDS(x);
cur--;
}
return tot;
}
int main() {
fast;
//freopen("input.txt", "r", stdin);
//freopen("outbad.txt", "w", stdout);
int t=1;
//cin >> t;
while (t--) {
arr.clear();
q.clear();
cin >> n >> k;
foru(i, 0, n)cin >> a[i];
ll ts = 0;
bool f = 1, pos = 0;
vector<ll> v;
foru(i, 0, n) {
if (f) {
pos = (a[i] >= 0);
ts += a[i];
f = 0;
}
else {
if ((a[i] >= 0) != (a[i - 1] >= 0)) {
pos = !pos;
v.pb(ts);
ts = a[i];
}
else ts += a[i];
}
}
v.pb(ts);
cout << solve(v) << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
2668 KB |
Output is correct |
2 |
Correct |
35 ms |
2668 KB |
Output is correct |
3 |
Correct |
39 ms |
2668 KB |
Output is correct |
4 |
Correct |
36 ms |
2668 KB |
Output is correct |
5 |
Correct |
34 ms |
2668 KB |
Output is correct |
6 |
Correct |
34 ms |
2668 KB |
Output is correct |
7 |
Correct |
35 ms |
2668 KB |
Output is correct |
8 |
Correct |
38 ms |
2668 KB |
Output is correct |
9 |
Correct |
35 ms |
2668 KB |
Output is correct |
10 |
Correct |
35 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2668 KB |
Output is correct |
2 |
Correct |
24 ms |
2668 KB |
Output is correct |
3 |
Correct |
23 ms |
2668 KB |
Output is correct |
4 |
Correct |
24 ms |
2668 KB |
Output is correct |
5 |
Correct |
35 ms |
2668 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 |
2688 KB |
Output is correct |
9 |
Correct |
41 ms |
2668 KB |
Output is correct |
10 |
Correct |
26 ms |
2668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
439 ms |
23524 KB |
Output is correct |
2 |
Correct |
430 ms |
26212 KB |
Output is correct |
3 |
Correct |
426 ms |
26468 KB |
Output is correct |
4 |
Correct |
439 ms |
26340 KB |
Output is correct |
5 |
Correct |
437 ms |
26340 KB |
Output is correct |
6 |
Correct |
445 ms |
26596 KB |
Output is correct |
7 |
Correct |
427 ms |
26724 KB |
Output is correct |
8 |
Correct |
452 ms |
26468 KB |
Output is correct |
9 |
Correct |
447 ms |
26724 KB |
Output is correct |
10 |
Correct |
443 ms |
26724 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 |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 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 |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 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 |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
2 ms |
492 KB |
Output is correct |
26 |
Correct |
2 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
2 ms |
492 KB |
Output is correct |
29 |
Correct |
2 ms |
492 KB |
Output is correct |
30 |
Correct |
2 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
2668 KB |
Output is correct |
2 |
Correct |
35 ms |
2668 KB |
Output is correct |
3 |
Correct |
39 ms |
2668 KB |
Output is correct |
4 |
Correct |
36 ms |
2668 KB |
Output is correct |
5 |
Correct |
34 ms |
2668 KB |
Output is correct |
6 |
Correct |
34 ms |
2668 KB |
Output is correct |
7 |
Correct |
35 ms |
2668 KB |
Output is correct |
8 |
Correct |
38 ms |
2668 KB |
Output is correct |
9 |
Correct |
35 ms |
2668 KB |
Output is correct |
10 |
Correct |
35 ms |
2668 KB |
Output is correct |
11 |
Correct |
23 ms |
2668 KB |
Output is correct |
12 |
Correct |
24 ms |
2668 KB |
Output is correct |
13 |
Correct |
23 ms |
2668 KB |
Output is correct |
14 |
Correct |
24 ms |
2668 KB |
Output is correct |
15 |
Correct |
35 ms |
2668 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 |
2688 KB |
Output is correct |
19 |
Correct |
41 ms |
2668 KB |
Output is correct |
20 |
Correct |
26 ms |
2668 KB |
Output is correct |
21 |
Correct |
439 ms |
23524 KB |
Output is correct |
22 |
Correct |
430 ms |
26212 KB |
Output is correct |
23 |
Correct |
426 ms |
26468 KB |
Output is correct |
24 |
Correct |
439 ms |
26340 KB |
Output is correct |
25 |
Correct |
437 ms |
26340 KB |
Output is correct |
26 |
Correct |
445 ms |
26596 KB |
Output is correct |
27 |
Correct |
427 ms |
26724 KB |
Output is correct |
28 |
Correct |
452 ms |
26468 KB |
Output is correct |
29 |
Correct |
447 ms |
26724 KB |
Output is correct |
30 |
Correct |
443 ms |
26724 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 |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
1 ms |
364 KB |
Output is correct |
39 |
Correct |
1 ms |
364 KB |
Output is correct |
40 |
Correct |
1 ms |
364 KB |
Output is correct |
41 |
Correct |
1 ms |
364 KB |
Output is correct |
42 |
Correct |
1 ms |
364 KB |
Output is correct |
43 |
Correct |
1 ms |
364 KB |
Output is correct |
44 |
Correct |
1 ms |
364 KB |
Output is correct |
45 |
Correct |
1 ms |
364 KB |
Output is correct |
46 |
Correct |
1 ms |
364 KB |
Output is correct |
47 |
Correct |
1 ms |
364 KB |
Output is correct |
48 |
Correct |
1 ms |
364 KB |
Output is correct |
49 |
Correct |
1 ms |
364 KB |
Output is correct |
50 |
Correct |
1 ms |
364 KB |
Output is correct |
51 |
Correct |
1 ms |
492 KB |
Output is correct |
52 |
Correct |
1 ms |
512 KB |
Output is correct |
53 |
Correct |
1 ms |
492 KB |
Output is correct |
54 |
Correct |
1 ms |
492 KB |
Output is correct |
55 |
Correct |
2 ms |
492 KB |
Output is correct |
56 |
Correct |
2 ms |
492 KB |
Output is correct |
57 |
Correct |
1 ms |
492 KB |
Output is correct |
58 |
Correct |
2 ms |
492 KB |
Output is correct |
59 |
Correct |
2 ms |
492 KB |
Output is correct |
60 |
Correct |
2 ms |
492 KB |
Output is correct |
61 |
Correct |
308 ms |
26084 KB |
Output is correct |
62 |
Correct |
201 ms |
26724 KB |
Output is correct |
63 |
Correct |
429 ms |
26084 KB |
Output is correct |
64 |
Correct |
277 ms |
26596 KB |
Output is correct |
65 |
Correct |
345 ms |
26596 KB |
Output is correct |
66 |
Correct |
368 ms |
26468 KB |
Output is correct |
67 |
Correct |
353 ms |
26156 KB |
Output is correct |
68 |
Correct |
458 ms |
26596 KB |
Output is correct |
69 |
Correct |
417 ms |
26084 KB |
Output is correct |
70 |
Correct |
433 ms |
25964 KB |
Output is correct |