제출 #1225596

#제출 시각아이디문제언어결과실행 시간메모리
1225596nhq0914K blocks (IZhO14_blocks)C++17
100 / 100
127 ms1888 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; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector <int> a(n + 1), dp(n + 1); F(i, 1, n) cin >> a[i], dp[i] = max(dp[i - 1], a[i]); F(_k, 2, k) { vector <int> tdp(n + 1, 2e9); stack <array <int, 2>> s; F(i, _k, n) { int min_f = dp[i - 1]; while(N(s) && a[s.top()[0]] <= a[i]) { min_f = min(min_f, s.top()[1]); s.pop(); } tdp[i] = min_f + a[i]; if(N(s)) tdp[i] = min(tdp[i], tdp[s.top()[0]]); s.push({i, 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...