제출 #1182540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182540		quannnguyen2009	K blocks (IZhO14_blocks)	C++20	100 / 100	219 ms	5144 KiB

blocks

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1e5+5, mod = 1e9+7, inf = 1e18;

int n, k;
int a[N];
int dp[N], tmp[N];

struct It {
    int id, d, mn;
};

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) tmp[i] = max(tmp[i-1], a[i]);
    tmp[0] = inf;
    // for (int i=1; i<=n; i++) cout << tmp[i] << " ";
    // cout << '\n';
    for (int j=2; j<=k; j++) {
        vector<It> v;
        dp[0] = inf;
        for (int i=1; i<=n; i++) {
            if(!sz(v) || a[i]<a[v.back().id]) {
                v.pb({i, tmp[i-1], (sz(v) ? min(v.back().mn, tmp[i-1]+a[i]) : tmp[i-1]+a[i])});
            } else {
                int dp_mn = inf;
                while(sz(v) && a[i]>=a[v.back().id]) {
                    dp_mn = min(dp_mn, v.back().d);
                    v.pop_back();
                }
                dp_mn = min(dp_mn, tmp[i-1]);
                // cout << tmp[i-1] << '\n';
                v.pb({i, dp_mn, (sz(v) ? min(v.back().mn, dp_mn+a[i]) : dp_mn+a[i])});
            }
            if(i>=j) dp[i] = v.back().mn;
            else dp[i] = inf;
            // for (auto [a, b, c]: v) cout << a << " " << b << " " << c << '\n';
            // cout << '\n';
        }
        for (int i=0; i<=n; i++) {
            tmp[i] = dp[i];
            // cout << dp[i] << " ";
        }
    }
    cout << tmp[n];
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47