Submission #338098

#TimeUsernameProblemLanguageResultExecution timeMemory
338098Dilshod_ImomovK blocks (IZhO14_blocks)C++17
100 / 100
217 ms81516 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 = 1e5 + 7; const int mod = 1e9 + 7; int a[N], dp[105][N]; int32_t main() { speed; int n, k; cin >> n >> k; for ( int i = 1; i <= n; i++ ) { cin >> a[i]; } for ( int i = 1; i <= n; i++ ) { dp[0][i] = 1e9; } stack < pair < int, int > > st; for ( int i = 1; i <= k; i++ ) { while ( !st.empty() ) { st.pop(); } dp[i][i] = dp[i - 1][i - 1] + a[i]; st.push( { a[i], dp[i - 1][i - 1] } ); for ( int j = i + 1; j <= n; j++ ) { int x = dp[i - 1][j - 1]; while ( !st.empty() && st.top().fi <= a[j] ) { x = min( x, st.top().se ); st.pop(); } if ( st.empty() || st.top().fi + st.top().se > a[j] + x ) { st.push( { a[j ], x } ); } dp[i][j] = st.top().fi + st.top().se; } } cout << dp[k][n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...