Submission #1208048

#TimeUsernameProblemLanguageResultExecution timeMemory
1208048gatapdevK blocks (IZhO14_blocks)C++20
0 / 100
1 ms328 KiB
#include<bits/stdc++.h> using namespace std; int a[100001]; int dp[10001][101]; int main(){ int n,K; cin>>n>>K; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++) for(int j=1;j<=K;j++) dp[i][j]=INT_MAX; for(int i=1;i<=n;i++) dp[i][1]=max(dp[i-1][1],a[i]); for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ int mx=-1; for(int k=j;k<=i;k++) mx=max(mx,a[k]); for(int k=2;k<=min(i,K);k++){ if(j>1) dp[i][k]=min(dp[i][k],dp[j-1][k-1]+mx); } } } cout<<dp[n][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...