Submission #1090813

#TimeUsernameProblemLanguageResultExecution timeMemory
1090813nguyennhK blocks (IZhO14_blocks)C++14
0 / 100
0 ms600 KiB
#include<bits/stdc++.h> #define el '\n' using namespace std ; const int MN = 1e5 + 5; const int64_t inf = 1e18; int64_t a[MN]; int32_t main (){ ios_base::sync_with_stdio(0); cin.tie(0); int n , k; cin >> n >> k; for ( int i = 1 ; i <= n ; i++ ) cin >> a[i]; vector<vector<int64_t>> dp(n + 5 , vector<int64_t>(k + 5 , inf)); dp[0][0] = 0; for ( int i = 1 ; i <= n ; i++ ){ int64_t mx = 0; // for ( int j = i ; j >= 1 ; j-- ){ // mx = max(mx , a[j]); // for ( int l = 0 ; l <= k ; l++ ){ // dp[i][l + 1] = min(dp[i][l + 1] , dp[j - 1][l] + mx); // } // } int pos = 1; for (int j = i ; j >= 1 ; j--){ if (a[j] > a[i]){ pos = j; break; } } for (int j = i ; j >= pos ; j--){ mx = max(mx , a[j]); for (int l = 0 ; l <= k ; l++){ dp[i][l + 1] = min(dp[i][l + 1] , dp[j - 1][l] + mx); } } } 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...