Submission #1239137

#TimeUsernameProblemLanguageResultExecution timeMemory
1239137MasterDebaterK blocks (IZhO14_blocks)C++20
53 / 100
1093 ms5704 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),INF=1e18; ll n,k,a[N],dp[N][2]; vector<pii>v; multiset<ll>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'; ll zd=INF; while(!v.empty() and v.back().S<a[i]){ //cout<<v.back().F<<' '<<v.back().S<<'\n'; pii nxt=v.back(); v.pop_back(); zd=min(zd,nxt.F); s.erase(s.find(nxt.F+nxt.S)); } if(zd!=INF){ v.push_back({zd,a[i]}); s.insert(zd+a[i]); } dp[i][1]=(*s.begin()); v.push_back({dp[i][0],0}); s.insert(dp[i][0]); } for(int i=0;i<n;i++)dp[i][0]=dp[i][1]; //for(int i=0;i<n;i++)cout<<dp[i][0]<<' '; //cout<<'\n'; } cout<<dp[n-1][0]; return 0; }

Compilation message (stderr)

blocks.cpp:7:36: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int N=1e5+10,off=(1<<17),INF=1e18;
      |                                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...