Submission #337925

#TimeUsernameProblemLanguageResultExecution timeMemory
337925Dilshod_ImomovK blocks (IZhO14_blocks)C++17
53 / 100
2 ms876 KiB
# include <bits/stdc++.h> # define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) # define int long long # define fi first # define se second using namespace std; const int N = 1e3 + 7; const int mod = 1e9 + 7; int a[N], dp[N][N]; int32_t main() { speed; int n, k; cin >> n >> k; for ( int i = 1; i <= n; i++ ) { cin >> a[i]; } for ( int i = 0; i <= n; i++ ) { for ( int j = 0; j <= k; j++ ) { dp[i][j] = 1e9; } } dp[0][0] = 0; for ( int i = 1; i <= n; i++ ) { for ( int j = 1; j <= min( i, k ); j++ ) { int mx = a[i]; for ( int x = i - 1; x >= 0; x-- ) { dp[i][j] = min( dp[i][j], dp[x][j - 1] + mx ); mx = max( a[x], mx ); } // cout << i << ' ' << j << ' ' << dp[i][j] << endl; } } 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...