#include <bits/stdc++.h>
using namespace std;
template<typename T> struct LinkedList;
void attemptMergeNext(LinkedList<long long>& list, int ind);
template<typename T> struct LinkedList{
int frontInd = -1;
int backInd = -1;
struct Node{
int next = -1;
int prev = -1;
int version = 0;
T val;
Node(){}
Node(T val){
this->val = val;
}
};
vector<Node> nodes;
void erase(int ind){
nodes[ind].version++;
if(nodes[ind].next != -1){
nodes[nodes[ind].next].prev = nodes[ind].prev;
}
if(nodes[ind].prev != -1){
nodes[nodes[ind].prev].next = nodes[ind].next;
}
if(frontInd == ind){
frontInd = nodes[ind].next;
}
if(backInd == ind){
backInd = nodes[ind].prev;
}
if(nodes[ind].prev != -1){
attemptMergeNext(*this, nodes[ind].prev);
}
}
void mergeNext(int ind){
assert(nodes[ind].next != -1);
nodes[ind].val += nodes[nodes[ind].next].val;
nodes[ind].version++;
erase(nodes[ind].next);
}
void append(T val){
Node node = Node(val);
int ind = nodes.size();
if(backInd == -1){
frontInd = ind;
}else{
nodes[backInd].next = ind;
node.prev = backInd;
}
backInd = ind;
nodes.push_back(node);
if(node.prev != -1){
attemptMergeNext(*this, node.prev);
}
}
T& front(){
return nodes[frontInd].val;
}
T& back(){
return nodes[backInd].val;
}
Node get(int ind){
return nodes[ind];
}
};
void attemptMergeNext(LinkedList<long long>& list, int ind){
int nextInd = list.nodes[ind].next;
if(nextInd == -1) return;
bool merge = (list.nodes[ind].val == 0 || list.nodes[nextInd].val == 0 || (!((list.nodes[ind].val > 0) ^ (list.nodes[nextInd].val > 0))));
if(merge){
list.mergeNext(ind);
}
}
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, k;
cin>>n>>k;
vector<int> a;
for(int i=0; i<n; i++){
int curA;
cin>>curA;
if(curA == 0) continue;
a.push_back(curA);
}
if(a.empty()){
cout<<0;
return 0;
}
n = a.size();
LinkedList<long long> segments;
segments.append(a.front());
for(int i=1; i<n; i++){
segments.append(a[i]);
}
if(segments.front() < 0){
segments.erase(segments.frontInd);
}
if(segments.frontInd == -1){
cout<<0;
return 0;
}
if(segments.back() < 0){
segments.erase(segments.backInd);
}
if(segments.backInd == -1){
cout<<0;
return 0;
}
long long ans = 0;
int segCount = 0;
priority_queue<pair<long long, pair<int, int>>> elemsToErase;
int ind = segments.frontInd;
while(ind != -1){
long long val = segments.get(ind).val;
if(val < 0){
elemsToErase.push({val, {ind, segments.get(ind).version}});
}else{
ans += val;
segCount++;
elemsToErase.push({-val, {ind, segments.get(ind).version}});
}
if(segCount > k){
while(true){
pair<long long, pair<int, int>> elem = elemsToErase.top();
elemsToErase.pop();
int node = elem.second.first;
if(segments.get(node).version != elem.second.second) continue;
long long val = segments.get(node).val;
if(val > 0){
ans -= val;
if(segments.get(node).prev != -1){
node = segments.get(node).prev;
segments.mergeNext(node);
}
if(segments.get(node).next != -1){
segments.mergeNext(node);
}
elemsToErase.push({segments.get(node).val, {node, segments.get(node).version}});
}else{
ans += val;
segments.erase(node);
if(segments.get(node).prev != -1){
node = segments.get(node).prev;
}else{
node = segments.frontInd;
}
elemsToErase.push({segments.get(node).val, {node, segments.get(node).version}});
}
break;
}
segCount--;
}
ind = segments.get(ind).next;
}
cout<<ans;
}
/*
3 1
2 -1 3
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |