제출 #871940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871940		12345678	K개의 묶음 (IZhO14_blocks)	C++17	0 / 100	2 ms	4548 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=105, lx=17;
int n, k, v[nx], dp[kx][nx], mx;

void solve(int l, int r, int ly, int optl, int optr)
{
    if (r<l) return;
    int md=(l+r)/2;
    //cout<<ly<<' '<<l<<' '<<md<<' '<<r<<' '<<optl<<' '<<optr<<'\n';
    pair<int, int> p={1e9, -1};
    mx=0;
    for (int i=md; i>optr; i--) mx=max(mx, v[i]);
    for (int i=min(optr, md); i>=optl; i--) mx=max(mx, v[i]), p=min(p, {mx+dp[ly-1][i-1], i});
    dp[ly][md]=p.first;
    solve(l, md-1, ly, optl, p.second);
    solve(md+1, r, ly, p.second, optr);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>k;
    for (int i=1; i<=n; i++) cin>>v[i], dp[0][i]=1e9;
    for (int i=1; i<=k; i++) dp[i][0]=1e9, solve(1, n, i, 1, n);
    //for (int i=1; i<=k; i++) for (int j=1; j<=n; j++) cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
    cout<<dp[k][n];
}

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