Submission #1225610

#TimeUsernameProblemLanguageResultExecution timeMemory
1225610nhq0914K blocks (IZhO14_blocks)C++17
100 / 100
98 ms1864 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() using namespace std; void read(int &n) { n = 0; char c = getchar(); while(isdigit(c)) { (n *= 10) += c - '0'; c = getchar(); } } const int maxn = 1e5 + 1; int n, k, cnt, a[maxn], s[maxn][2], dp[maxn], tdp[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); read(n), read(k); F(i, 1, n) read(a[i]), dp[i] = max(dp[i - 1], a[i]); F(_k, 2, k) { cnt = 0; memset(tdp, 63, sizeof tdp); F(i, _k, n) { static int min_f; min_f = dp[i - 1]; while(cnt && a[s[cnt][0]] <= a[i]) { min_f = min(min_f, s[cnt][1]); --cnt; } tdp[i] = min_f + a[i]; if(cnt) tdp[i] = min(tdp[i], tdp[s[cnt][0]]); ++cnt; s[cnt][0] = i, s[cnt][1] = min_f; } swap(tdp, dp); } cout << dp[n]; 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...