Submission #1225613

#TimeUsernameProblemLanguageResultExecution timeMemory
1225613nhq0914K blocks (IZhO14_blocks)C++17
100 / 100
107 ms2664 KiB
#include <bits/stdc++.h> #define F(i, a, b) for(int i = (a); i <= (b); ++i) using namespace std; void read(int &n) { n = 0; char c = getchar(); while(isdigit(c)) { (n *= 10) += c - '0'; c = getchar(); } } const int maxn = 2e5 + 1; int n, k, cnt, min_f, a[maxn], s[maxn][2], dp[maxn], tdp[maxn]; int main() { 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) { 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]]); 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...