#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int, int>
set<pii> nums;
set<pii> absnums;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, k; cin >> n >> k;
bool ispos = true;
bool acceptneg = false;
int s = 0;
int idx = 0;
for (int i = 0; i < n; i++){
int g; cin >> g;
if (g > 0) {
acceptneg = true;
if (!ispos){
nums.insert({idx, s});
absnums.insert({llabs(s), idx});
s = 0;
ispos = true;
idx++;
}
s += g;
} else {
if (!acceptneg) continue;
if (ispos){
nums.insert({idx, s});
absnums.insert({llabs(s), idx});
s = 0;
ispos = false;
idx++;
}
s += g;
}
}
if (s > 0){
nums.insert({idx, s});
absnums.insert({s, idx});
}
while (nums.size() / 2 + 1 > k){
auto [s, idx] = *absnums.begin(); absnums.erase(absnums.begin());
auto itr = nums.lower_bound({idx - 1, 1e18});
auto [curridx, val] = *itr;
itr++;
if (itr != nums.end()){
auto [idx, nval] = *itr;
val += nval;
itr--;
absnums.erase({llabs(nval), idx});
nums.erase({idx, nval});
} else {
itr--;
}
if (itr != nums.begin()){
itr--;
auto [idx, pval] = *itr;
val += pval;
itr++;
absnums.erase({llabs(pval), idx});
nums.erase({idx, pval});
}
nums.erase(itr);
nums.insert({curridx, val});
if (val <= 0){
auto itr = nums.find({curridx, val});
if (itr == nums.begin()){
nums.erase(itr);
} else if ((++itr) == nums.end()){
--itr;
nums.erase(itr);
} else {
absnums.insert({llabs(val), curridx});
}
} else {
absnums.insert({llabs(val), curridx});
}
}
int ans = 0;
for (auto [idx, num] : nums){
if (num > 0) ans += num;
}
cout << ans << '\n';
Compilation message
feast.cpp: In function 'int32_t main()':
feast.cpp:42:32: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
42 | while (nums.size() / 2 + 1 > k){
| ~~~~~~~~~~~~~~~~~~~~^~~
feast.cpp:84:24: error: expected '}' at end of input
84 | cout << ans << '\n';
| ^
feast.cpp:7:16: note: to match this '{'
7 | int32_t main() {
| ^
