#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 long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int sz = 3e5;
int k, n;
ll a[sz];
map<ld, pair<ll, bool>> arr; //pos, val, isNeg
set<pair<ll, pair<ld, bool>>> q;//val, pos, isNeg
inline pair<ld, pair<ll, bool>> qToArr(pair<ll, pair<ld, bool>> x) {
return { x.second.first, {x.first,x.second.second} };
}
inline pair<ll, pair<ld, bool>> arrToQ(pair<ld, pair<ll, bool>> x) {
return { x.second.first,{x.first,x.second.second} };
}
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<ld, bool>> x) {
auto y = arr.find(x.second.first), yp = y, ym = y;
yp++;
ym--;
if (x.second.second) {
ll nval = yp->second.first + ym->second.first + x.first;
q.erase(arrToQ(*yp));
q.erase(arrToQ(*ym));
q.erase(x);
q.insert({ nval,{x.second.first,0} });
arr[x.second.first] = { 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,{x.second.first,1} });
arr[x.second.first] = { 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,i & 1} });
}
int cur = vsz / 2 + 1;
while (cur > k) {
auto x = *q.begin();
tot -= x.first;
removeFromDS(x);
cur--;
}
return tot;
}
int main() {
fast;
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
2668 KB |
Output is correct |
2 |
Correct |
34 ms |
2668 KB |
Output is correct |
3 |
Correct |
35 ms |
2668 KB |
Output is correct |
4 |
Correct |
35 ms |
2668 KB |
Output is correct |
5 |
Correct |
35 ms |
2688 KB |
Output is correct |
6 |
Correct |
34 ms |
2668 KB |
Output is correct |
7 |
Correct |
38 ms |
2668 KB |
Output is correct |
8 |
Correct |
34 ms |
2796 KB |
Output is correct |
9 |
Correct |
34 ms |
2668 KB |
Output is correct |
10 |
Correct |
34 ms |
2668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
2668 KB |
Output is correct |
2 |
Correct |
23 ms |
2668 KB |
Output is correct |
3 |
Correct |
23 ms |
2668 KB |
Output is correct |
4 |
Correct |
23 ms |
2668 KB |
Output is correct |
5 |
Correct |
36 ms |
2796 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 |
2668 KB |
Output is correct |
9 |
Correct |
36 ms |
2668 KB |
Output is correct |
10 |
Correct |
23 ms |
2668 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
505 ms |
30436 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
33 ms |
2668 KB |
Output is correct |
2 |
Correct |
34 ms |
2668 KB |
Output is correct |
3 |
Correct |
35 ms |
2668 KB |
Output is correct |
4 |
Correct |
35 ms |
2668 KB |
Output is correct |
5 |
Correct |
35 ms |
2688 KB |
Output is correct |
6 |
Correct |
34 ms |
2668 KB |
Output is correct |
7 |
Correct |
38 ms |
2668 KB |
Output is correct |
8 |
Correct |
34 ms |
2796 KB |
Output is correct |
9 |
Correct |
34 ms |
2668 KB |
Output is correct |
10 |
Correct |
34 ms |
2668 KB |
Output is correct |
11 |
Correct |
25 ms |
2668 KB |
Output is correct |
12 |
Correct |
23 ms |
2668 KB |
Output is correct |
13 |
Correct |
23 ms |
2668 KB |
Output is correct |
14 |
Correct |
23 ms |
2668 KB |
Output is correct |
15 |
Correct |
36 ms |
2796 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 |
2668 KB |
Output is correct |
19 |
Correct |
36 ms |
2668 KB |
Output is correct |
20 |
Correct |
23 ms |
2668 KB |
Output is correct |
21 |
Incorrect |
505 ms |
30436 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |