Submission #558557

#TimeUsernameProblemLanguageResultExecution timeMemory
558557stefantagaFeast (NOI19_feast)C++14
12 / 100
1014 ms10728 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,i,k; ll v[300005],din[300005],cnt[300005],sum[300005]; ll suma(int st,int dr) { return sum[dr]-sum[st-1]; } ll ok (ll mij) { deque <int> st; st.push_back(0); for (i=1; i<=n; i++) { din[i]=din[i-1]; cnt[i]=cnt[i-1]; if (din[i]<din[i-1]+mij) { din[i]=din[i-1]+mij; cnt[i]=cnt[i-1]+1; } if (st.empty()) { if (din[i]<v[i]+din[i-1]+mij) { din[i]=v[i]+din[i-1]+mij; cnt[i]=1+cnt[i-1]; } } else { if (din[i]<din[st.front()]+suma(st.front()+1,i)+mij) { din[i]=din[st.front()]+suma(st.front()+1,i)+mij; cnt[i]=1+cnt[st.front()]; } } while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i]) { st.pop_back(); } st.push_back(i); } return cnt[n]; } ll st,dr,sol; int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n>>k; for (i=1; i<=n; i++) { cin>>v[i]; sum[i]=sum[i-1]+v[i]; } st=-1e9; dr=1e9; int nr=200; for (;nr--;) { ll mij = (st+dr)/2; auto salut = ok(mij); if (salut>=k) { sol=mij; dr=mij; } else { st=mij; } } auto salut = ok(0); deque <int> st; st.push_back(0); for (i=1; i<=n; i++) { din[i]=din[i-1]; cnt[i]=cnt[i-1]; if (din[i]<din[i-1]+sol) { din[i]=din[i-1]+sol; cnt[i]=cnt[i-1]+1; } if (st.empty()) { if (din[i]<v[i]+din[i-1]+sol) { din[i]=v[i]+din[i-1]+sol; cnt[i]=1+cnt[i-1]; } } else { int poz=st.front(); if (din[i]<din[poz]+suma(poz+1,i)+sol) { din[i]=din[poz]+suma(poz+1,i)+sol; cnt[i]=1+cnt[poz]; } } while (!st.empty()&&din[st.back()]+suma(st.back()+1,i+1)<=v[i+1]+din[i]) { st.pop_back(); } st.push_back(i); } cout<<din[n]-cnt[n]*sol; return 0; }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:80:10: warning: unused variable 'salut' [-Wunused-variable]
   80 |     auto salut = ok(0);
      |          ^~~~~
#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...