Submission #1239111

#TimeUsernameProblemLanguageResultExecution timeMemory
1239111MasterDebaterK blocks (IZhO14_blocks)C++20
0 / 100
0 ms328 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<ll,ll> #define F first #define S second const int N=1e5+10,off=(1<<17); int n,k,a[N],dp[N][2]; vector<pii>v; multiset<int>s; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>k; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<n;i++){ if(i==0)dp[i][0]=a[i]; else dp[i][0]=max(dp[i-1][0],a[i]); } for(int j=1;j<k;j++){ //cout<<"------------------\n"; v.clear(); v.push_back({dp[j-1][0],0}); s.clear(); s.insert(dp[j-1][0]); for(int i=j;i<n;i++){ //cout<<i<<'\n'; int zd=-1; while(!v.empty() and v.back().S<a[i]){ //cout<<"v sz: "<<v.size()<<'\n'; pii nxt=v.back(); v.pop_back(); zd=nxt.F; s.erase(s.find(nxt.F+nxt.S)); } if(zd!=-1){ v.push_back({zd,a[i]}); s.insert(zd+a[i]); } dp[i][1]=(*s.begin()); v.push_back({dp[i][1],0}); s.insert(dp[i][1]); } for(int i=0;i<n;i++)dp[i][0]=dp[i][1]; } cout<<dp[n-1][0]; return 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...