Submission #1186122

#TimeUsernameProblemLanguageResultExecution timeMemory
1186122PieArmyK blocks (IZhO14_blocks)C++20
100 / 100
260 ms82400 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; const ll inf=1000000000000; int n,k; ll arr[100023]; int nex[100023]; ll dp[100023][101]; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n>>k; for(int i=1;i<=n+1;i++){ for(int j=0;j<=k;j++){ dp[i][j]=inf; } } dp[1][0]=0; for(int i=1;i<=n;i++){ cin>>arr[i]; } arr[n+1]=inf; vector<int>sta={n+1}; for(int i=n;i>=1;i--){ while(arr[sta.back()]<=arr[i]){ sta.pop_back(); } nex[i]=sta.back(); sta.pb(i); } for(int i=0;i<=k;i++){ vector<pair<int,ll>>v; for(int j=1;j<=n+1;j++){ if(v.size()){ dp[j][i]=min(dp[j][i],v.back().sc); } while(v.size()&&arr[v.back().fr]<arr[j]){ v.pop_back(); } if(i){ v.pb({j,dp[j][i-1]}); if(v.size()>1){ v.back().sc=min(v.back().sc,v[v.size()-2].sc); } } if(j==n+1)continue; if(nex[j]!=n+1){ dp[nex[j]][i]=min(dp[nex[j]][i],dp[j][i]); } dp[j][i]+=arr[j]; } } cout<<dp[n+1][k]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...