Submission #1225572

#TimeUsernameProblemLanguageResultExecution timeMemory
1225572nhq0914K blocks (IZhO14_blocks)C++17
100 / 100
154 ms40652 KiB
#include <bits/stdc++.h> #define F(i, a, b) for(int i = (a); i <= (b); ++i) #define R(i, a, b) for(int i = (a); i >= (b); --i) #define N(a) (int)a.size() #define ll long long using namespace std; int n, k, a[100001], dp[100001][101]; stack <pair <int, int>> s; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; F(i, 1, n) cin >> a[i]; memset(dp, 63, sizeof dp); dp[0][1] = 0; F(i, 1, n) dp[i][1] = max(dp[i - 1][1], a[i]); F(j, 2, k) { while(N(s)) s.pop(); F(i, j, n) { int min_f = dp[i - 1][j - 1]; while(N(s) && a[s.top().first] <= a[i]) { min_f = min(min_f, s.top().second); s.pop(); } dp[i][j] = min(dp[N(s) ? s.top().first : 0][j], min_f + a[i]); s.push({i, min_f}); } } 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...