Submission #88512

#	Time	Username	Problem	Language	Result	Execution time	Memory
88512		ABCD	K개의 묶음 (IZhO14_blocks)	C++14	53 / 100	1058 ms	1276 KiB

blocks

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N=1e5+5;
const int oo=1e8+5;

int m;
int n,k;
int a[N];
int IT[N*8];
int F[N][105];


void build(int k,int l,int r){
    if(l>r) return;
    if(l==r){
        IT[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    IT[k]=max(IT[k*2],IT[k*2+1]);
}

int getmax(int k,int l,int r,int u,int v){
    if(r<u||l>v)
        return 0;
    if(l>=u&&r<=v)
        return IT[k];
    int mid=(l+r)/2;
    return max(getmax(k*2,l,mid,u,v),getmax(k*2+1,mid+1,r,u,v));
}

/*
void Solve(){
    FOR(i,1,k) FOR(j,i,n)
        F[i][j]=F[i-1][j-1]+getmax(1,1,n,j,n);
    cout<<F[k][n];
}*/

int Try(int n,int k){
    if(k==1) return getmax(1,1,m,1,n);
    if(F[n][k]) return F[n][k];
    int tmp=oo+5;
    for(int i=n;i>=max(2,k);i--){
        int t=getmax(1,1,m,i,n);
        tmp=min(tmp,t+Try(i-1,k-1));
    }
    F[n][k]=tmp;
    return F[n][k];
}

main(){
    //freopen("blocks.in","r",stdin);
    //freopen("blocks.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    FOR(i,1,n) cin>>a[i];
    build(1,1,n);
    m=n;
    cout<<Try(n,k);
}

Compilation message (stderr)

blocks.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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