제출 #1019265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1019265		andrewp	K개의 묶음 (IZhO14_blocks)	C++14	53 / 100	39 ms	39532 KiB

blocks

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array
#define DBG(x) cout << #x << "= " << x << "\n"

const int mxN=1e5;
const ll inf=(ll)(1e18);
int n, k;
ll a[mxN], dp[mxN][105];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n >> k;
    for(int i=1; i<=n; ++i) cin >> a[i];
    for(int i=0; i<=n; ++i) {
        for(int j=0; j<=k; ++j) dp[i][j]=inf;
    }
    ll mx=a[1];
    for(int i=1; i<=n; ++i) {
        mx=max(mx, a[i]);
        dp[i][1]=mx;
    }
    for(int j=2; j<=k; ++j) {
        stack<ar<ll, 2>> stk;
        for(int i=1; i<=n; ++i) {
            ll upd=dp[i-1][j-1];
            while(!stk.empty()&&stk.top()[0]<a[i]) {
                upd=min(upd, stk.top()[1]);
                stk.pop();
            }
            if(stk.empty() || a[i]+upd<stk.top()[0]+stk.top()[1]) {
                stk.push({a[i], upd});
            }
            if(j>i) continue;
            dp[i][j]=stk.top()[0]+stk.top()[1];
        }
    }
    cout << dp[n][k] << "\n";
	return 0;
}

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