Submission #1229268

#TimeUsernameProblemLanguageResultExecution timeMemory
1229268pumkinheadFeast (NOI19_feast)C++20
4 / 100
43 ms15324 KiB
#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){ Node& node = nodes[ind]; node.version++; if(node.next != -1){ nodes[node.next].prev = node.prev; } if(node.prev != -1){ nodes[node.prev].next = node.next; } if(frontInd == ind){ frontInd = node.next; } if(backInd == ind){ backInd = node.prev; } if(node.prev != -1){ attemptMergeNext(*this, node.prev); } } void mergeNext(int ind){ Node& node = nodes[ind]; node.val += nodes[node.next].val; node.version++; erase(node.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; } 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; segments.mergeNext(node); if(segments.get(node).prev != -1){ node = segments.get(node).prev; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...