제출 #1265541

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1265541		rayan_bd	K blocks (IZhO14_blocks)	C++20	0 / 100	0 ms	328 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int N, K;
vector<int> A;
vector<ll> dpPrev, dpCur;

void compute(int k, int L, int R, int optL, int optR) {
    if (L > R) return;
    int mid = (L + R) >> 1;
    pair<ll,int> best = {INF, -1};

    ll curMax = 0;
    for (int j = min(mid-1, optR); j >= optL; j--) {
        curMax = max(curMax, (ll)A[j+1]);
        ll val = dpPrev[j] + curMax;
        if (val < best.first) best = {val, j};
    }
    dpCur[mid] = best.first;
    int opt = best.second;

    compute(k, L, mid-1, optL, opt);
    compute(k, mid+1, R, opt, optR);
}

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

    cin >> N >> K;
    A.resize(N+1);
    for (int i=1; i<=N; i++) cin >> A[i];

    dpPrev.assign(N+1, INF);
    dpCur.assign(N+1, INF);

    ll curMax = 0;
    for (int i=1; i<=N; i++) {
        curMax = max(curMax, (ll)A[i]);
        dpPrev[i] = curMax;
    }

    for (int k=2; k<=K; k++) {
        compute(k, 1, N, 0, N-1);
        dpPrev = dpCur;
        fill(dpCur.begin(), dpCur.end(), INF);
    }

    cout << dpPrev[N] << "\n";
}

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