oj.uz

Submission #16187

# Submission time Handle Problem Language Result Execution time Memory
16187 2015-08-16T08:50:21 Z jihoon K blocks (IZhO14_blocks) C++
53 / 100
 1000 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(ss<=ee){
        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(0,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++;
        //printf("%d %d\n",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,st[j].first-1,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
14.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 Correct 0 ms 109120 KB Output is correct
6 Correct 0 ms 109120 KB Output is correct
7 Correct 0 ms 109120 KB Output is correct
8 Correct 0 ms 109120 KB Output is correct
9 Correct 0 ms 109120 KB Output is correct
10 Correct 0 ms 109120 KB Output is correct
11 Correct 0 ms 109120 KB Output is correct
12 Correct 0 ms 109120 KB Output is correct
13 Correct 0 ms 109120 KB Output is correct
14 Correct 0 ms 109120 KB Output is correct
15 Correct 0 ms 109120 KB Output is correct
16 Correct 0 ms 109120 KB Output is correct
17 Correct 0 ms 109120 KB Output is correct
18 Correct 0 ms 109120 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 0 ms 109120 KB Output is correct
6 Correct 0 ms 109120 KB Output is correct
7 Correct 0 ms 109120 KB Output is correct
8 Correct 0 ms 109120 KB Output is correct
9 Correct 0 ms 109120 KB Output is correct
10 Correct 0 ms 109120 KB Output is correct
11 Correct 0 ms 109120 KB Output is correct
12 Correct 0 ms 109120 KB Output is correct
13 Correct 0 ms 109120 KB Output is correct
14 Correct 0 ms 109120 KB Output is correct
15 Correct 0 ms 109120 KB Output is correct
16 Correct 0 ms 109120 KB Output is correct
17 Correct 0 ms 109120 KB Output is correct
18 Correct 0 ms 109120 KB Output is correct
19 Correct 0 ms 109120 KB Output is correct
20 Correct 0 ms 109120 KB Output is correct

Subtask #3
21.0 / 21.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 Correct 0 ms 109120 KB Output is correct
6 Correct 0 ms 109120 KB Output is correct
7 Correct 0 ms 109120 KB Output is correct
8 Correct 0 ms 109120 KB Output is correct
9 Correct 0 ms 109120 KB Output is correct
10 Correct 0 ms 109120 KB Output is correct
11 Correct 0 ms 109120 KB Output is correct
12 Correct 0 ms 109120 KB Output is correct
13 Correct 0 ms 109120 KB Output is correct
14 Correct 0 ms 109120 KB Output is correct
15 Correct 4 ms 109120 KB Output is correct
16 Correct 0 ms 109120 KB Output is correct
17 Correct 0 ms 109120 KB Output is correct
18 Correct 4 ms 109120 KB Output is correct
19 Correct 5 ms 109120 KB Output is correct

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 109120 KB Output is correct
2 Correct 10 ms 109120 KB Output is correct
3 Correct 36 ms 109120 KB Output is correct
4 Correct 298 ms 109120 KB Output is correct
5 Execution timed out 1000 ms 109120 KB Program timed out
6 Halted 0 ms 0 KB -