oj.uz

Submission #16186

# Submission time Handle Problem Language Result Execution time Memory
16186 2015-08-16T08:38:52 Z jihoon K blocks (IZhO14_blocks) C++
0 / 100
 0 ms 109120 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 109120 KB Output is correct
2 Correct 0 ms 109120 KB Output is correct
3 Correct 0 ms 109120 KB Output is correct
4 Correct 0 ms 109120 KB Output is correct
5 Incorrect 0 ms 109120 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -