Submission #882746

#TimeUsernameProblemLanguageResultExecution timeMemory
882746AcanikolicK blocks (IZhO14_blocks)C++14
53 / 100
1043 ms10076 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define F first #define S second using namespace std; const int N = 1e5 + 10; const int inf = 1e18; int dp[N][110],a[N]; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[i][1] = max(dp[i-1][1],a[i]); } for(int i = 1; i <= n; i++) { for(int j = 2; j <= k; j++) dp[i][j] = inf; } for(int i = 1; i <= n; i++) { for(int j = 2; j <= i; j++) { int mx = a[i]; for(int ii = i; ii >= 1; ii--) { if(ii < j) break; mx = max(mx,a[ii]); dp[i][j] = min(dp[i][j],dp[ii-1][j-1] + mx); } } } cout << dp[n][k]; 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...