# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
980898 | 2024-05-12T15:29:04 Z | happy_node | Cake 3 (JOI19_cake3) | C++17 | 1 ms | 2392 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX=2e5+5; int N,M; ll V[MX],C[MX]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>N>>M; for(int i=1;i<=N;i++) cin>>V[i]>>C[i]; vector<int> ord; for(int i=1;i<=N;i++) ord.push_back(i); sort(ord.begin(),ord.end(),[&](int i, int j){ return C[i]<C[j]; }); multiset<ll> st; ll sum=0,ans=0; for(int i=1;i<=M;i++) st.insert(0); for(auto i:ord) { sum+=V[i]; st.insert(V[i]); sum-=*st.begin(); st.erase(st.begin()); ans=max(ans,sum-2*C[i]); // trying to insert Vi + 2Ci ll cur=0; while(st.size()) { if(cur+*st.rbegin()<V[i]+2*C[i]) { cur+=*st.rbegin(); sum-=*st.rbegin(); st.erase(st.find(*st.rbegin())); } else { ll k=*st.rbegin(); sum-=k; st.erase(st.find(k)); cur+=k; cur-=V[i]+2*C[i]; sum+=cur; st.insert(cur); break; } } sum+=V[i]+2*C[i]; st.insert(V[i]+2*C[i]); while(st.size()<M) st.insert(0); } cout<<ans<<'\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 2392 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |