제출 #1121090

#제출 시각아이디문제언어결과실행 시간메모리
1121090IcelastK개의 묶음 (IZhO14_blocks)C++17
0 / 100
1 ms596 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ int n, k; cin >> n >> k; vector<ll> a(n+1); for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<ll> f(n+1, INF), prv(n+1, INF); f[0] = 0; a[0] = INF; for(int j = 1; j <= k; j++){ prv = f; fill(f.begin(), f.end(), INF); stack<pair<int, ll>> st; st.push({0, INF}); for(int i = 1; i <= n; i++){ while(!st.empty() && a[st.top().first] <= a[i]){ st.pop(); } int l = st.top().first; ll mn = st.top().second; st.push({i, min(mn, prv[max(l, j-1)]+a[i])}); f[i] = st.top().second; } } cout << f[n]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...