제출 #1197426

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197426		huygd	K개의 묶음 (IZhO14_blocks)	C++20	53 / 100	1096 ms	4420 KiB

blocks

#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
using namespace std;
int n,k;
int a[100001];
int st[400001];
int dp[100001][101];
void upd(int id,int l,int r,int i,int v) {
    if (l>i||r<i) return;
    if (l==r) {
        st[id]=v;
        return;
    }
    int mid=(l+r)>>1;
    upd(id<<1,l,mid,i,v);
    upd(id<<1|1,mid+1,r,i,v);
    st[id]=max(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v) {
    if (l>v||r<u) return 0;
    if (l>=u&&r<=v) return st[id];
    int mid=(l+r)>>1;
    return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
int F(int x,int y) {
    if (dp[x][y]) return dp[x][y];
    if (y==k-1) return dp[x][y]=get(1,1,n,x,n);
    dp[x][y]=1e9;
    for (int i=x;i<=n+1-(k-y);++i) dp[x][y]=min(dp[x][y],get(1,1,n,x,i)+F(i+1,y+1));
    return dp[x][y];
}
int main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    cin>>n>>k;
    for (int i=1;i<=n;++i) {
        cin>>a[i];
        upd(1,1,n,i,a[i]);
    }
    cout<<F(1,0);
}

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