Submission #1090814

#TimeUsernameProblemLanguageResultExecution timeMemory
1090814nguyennhK blocks (IZhO14_blocks)C++14
53 / 100
1072 ms4956 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 >= 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); } } } cout << dp[n][k]; }

Compilation message (stderr)

blocks.cpp: In function 'int32_t main()':
blocks.cpp:26:9: warning: variable 'pos' set but not used [-Wunused-but-set-variable]
   26 |     int pos = 1;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...