Submission #134112

#TimeUsernameProblemLanguageResultExecution timeMemory
134112mirbek01K blocks (IZhO14_blocks)C++11
0 / 100
1064 ms40368 KiB
# include <bits/stdc++.h> using namespace std; const int N = 1e5 + 2; int n, a[N], k, dp[102][N]; int stk[N], pt, pf[N]; int main(){ cin >> n >> k; for(int i = 1; i <= n; i ++) cin >> a[i]; memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[1][1] = a[1]; for(int i = 2; i <= n; i ++){ dp[1][i] = max(dp[1][i - 1], a[i]); } for(int i = 2; i <= k; i ++){ int mx = 0; for(int j = i; j <= n; j ++){ for(int t = j; t >= i; t --){ mx = max(mx, a[t]); dp[i][j] = min(dp[i][j], dp[i - 1][t - 1] + mx); } } } cout << dp[k][n] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...