Submission #1186110

#TimeUsernameProblemLanguageResultExecution timeMemory
1186110PieArmyK blocks (IZhO14_blocks)C++20
53 / 100
1042 ms90420 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]; vector<ll>add[100023],sub[100023]; 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++){ map<ll,int>mp; for(int j=1;j<=n+1;j++){ for(ll x:add[j]){ mp[x]++; } add[j].clear(); for(ll x:sub[j]){ if(!--mp[x])mp.erase(x); } sub[j].clear(); if(mp.size())dp[j][i]=min(dp[j][i],mp.begin()->fr); if(j==n+1)continue; if(nex[j]!=n+1){ dp[nex[j]][i]=min(dp[nex[j]][i],dp[j][i]); } } for(int j=1;j<=n;j++){ add[j+1].pb(dp[j][i]+arr[j]); if(nex[j]!=n+1){ sub[nex[j]+1].pb(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...