Submission #1101451

#TimeUsernameProblemLanguageResultExecution timeMemory
1101451ngongocbichK blocks (IZhO14_blocks)C++17
53 / 100
1066 ms8784 KiB
#include <bits/stdc++.h> #define int long long #define mask(k) (1<<(k)) using namespace std; int n,k,a[1000001],dp[1001][1001],mx[1001][21]; int getmx(int l, int r) { int p=__lg(r-l+1); return max(mx[l][p],mx[r-mask(p)+1][p]); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("w.inp","r",stdin); // freopen("w.out","w",stdout); cin>>n>>k; for (int i=1; i<=n; i++) cin>>a[i],mx[i][0]=a[i]; for (int j=1; mask(j)<=n; j++) for (int i=1; i+mask(j)-1<=n; i++) mx[i][j]=max(mx[i][j-1],mx[i+mask(j-1)][j-1]); memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for (int i=1; i<=k; i++) for (int j=1; j<=n; j++) for (int p=1; p<=j; p++) dp[i][j]=min(dp[i][j],dp[i-1][p-1]+getmx(p,j)); cout<<dp[k][n]; 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...