Submission #16186

#	Time	Username	Problem	Language	Result	Execution time	Memory
16186		jihoon	K blocks (IZhO14_blocks)	C++98	0 / 100	0 ms	109120 KiB

blocks

#include<cstdio>
#include<vector>
#include<algorithm>
#define base 131072
using namespace std;
vector< pair<int,int> > st;
int stp=0;
int idxtree[105][262144]={0};
int su[100001];
int n,k;
int ans;

int getmn(int ss,int ee,int tm){
    int res=2100000000;
    ss+=base;ee+=base;
    while(1){
        if(ss%2){
            if(idxtree[tm][ss]>0) res=min(res,idxtree[tm][ss]);
            ss++;
        }
        if(ee%2==0){
            if(idxtree[tm][ee]>0) res=min(res,idxtree[tm][ee]);
            ee--;
        }
        if(ss>ee) break;
        ss/=2;ee/=2;
    }
    return res;
}

void update(int val,int where,int tm){
    where+=base;
    while(where>0){
        idxtree[tm][where]=val;
        if(where%2){
            if(idxtree[tm][where-1]<=val&&idxtree[tm][where-1]>0) break;
        }else{
            if(idxtree[tm][where+1]<=val&&idxtree[tm][where+1]>0) break;
        }
        where/=2;
    }
}

int main(){
    int i,j,t;
    stp=1;
    st.push_back(make_pair(-1,100000000));
    scanf("%d %d",&n,&k);
    for(i=0;i<n;i++) scanf("%d",&su[i]);
    for(i=0;i<n;i++){
        while(st[stp-1].second<su[i]){
            st.pop_back();
            stp--;
        }
        st.push_back(make_pair(i,su[i]));
        stp++;
        for(t=k-1;t>=1;t--){
            ans=2000000000;
            for(j=1;j<stp;j++){
                ans=min(ans,st[j].second+getmn(st[j-1].first+1,st[j].first,t));
            }
            update(ans,i,t+1);
            //printf("%d %d %d\n",i,t+1,ans);
        }
        update(st[1].second,i,1);
    }
    printf("%d",idxtree[k][n-1+base]);
}

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