Submission #13363

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13363	2015-02-13T17:23:15 Z	baneling100	Mountain Trek Route (IZhO12_route)	C++	40 / 100	209 ms	17612 KB

route

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define N_MAX 1000000

using namespace std;

typedef pair <int,int> ppair;
priority_queue <ppair,vector<ppair>,greater<ppair> > PQ;
int N, K, Ans;
int M, Block[N_MAX+1], Size[N_MAX+1];
int Left[N_MAX+1], Right[N_MAX+1];

int main(void) {

    int i, inp, t1, t2, h1, h2;

    scanf("%d %d",&N,&K);
    for(i=1 ; i<=N ; i++) {
        scanf("%d",&inp);
        if(Block[M]==inp) Size[M]++;
        else Block[++M]=inp, Size[M]=1;
    }
    if(M>1 && Block[1]==Block[M]) Size[1]+=Size[M--];
    if(M==1) {
        printf("0");
        return 0;
    }
    if(Block[M]>Block[1]) Left [1]=M;
    if(Block[1]<Block[2]) Right[1]=2;
    if(Left[1] && Right[1]) PQ.push(make_pair(Size[1],1));
    for(i=2 ; i<=M-1 ; i++) {
        if(Block[i-1]>Block[i  ]) Left [i]=i-1;
        if(Block[i  ]<Block[i+1]) Right[i]=i+1;
        if(Left[i] && Right[i]) PQ.push(make_pair(Size[i],i));
    }
    if(Block[M-1]>Block[M]) Left [M]=M-1;
    if(Block[M  ]<Block[1]) Right[M]=1;
    if(Left[M] && Right[M]) PQ.push(make_pair(Size[M],M));
    while(!PQ.empty()) {
        t1=PQ.top().first, t2=PQ.top().second, PQ.pop();
        h1=K/t1;
        h2=min(Block[Left[t2]],Block[Right[t2]])-Block[t2];
        if(h1<h2) {
            Ans+=h1<<1;
            break;
        }
        else {
            Ans+=h2<<1;
            K-=t1*h2;
            if(Block[Left[t2]]<Block[Right[t2]]) {
                Size [Left[t2]]+=Size [t2];
                Right[Left[t2]] =Right[t2];
                if(Left[Left[t2]]) PQ.push(make_pair(Size[Left[t2]],Left[t2]));
            }
            else if(Block[Left[t2]]>Block[Right[t2]]) {
                Size[Right[t2]]+=Size[t2];
                Left[Right[t2]] =Left[t2];
                if(Right[Right[t2]]) PQ.push(make_pair(Size[Right[t2]],Right[t2]));
            }
            else {
                Size [Left[t2]]+=Size[t2]+Size[Right[t2]];
                Right[Left[t2]] =Right[Right[t2]];
                Size[Right[t2]]+=Size[t2]+Size[Left[t2]];
                Left[Right[t2]] =Left[Left[t2]];
                if(Left[Left[t2]] && Right[Left[t2]]) PQ.push(make_pair(Size[Left[t2]],Left[t2]));
            }
        }
    }
    printf("%d",Ans);
    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	16840 KB	Output is correct
2	Correct	0 ms	16840 KB	Output is correct
3	Incorrect	0 ms	16840 KB	Output isn't correct
4	Correct	0 ms	16840 KB	Output is correct
5	Incorrect	0 ms	16840 KB	Output isn't correct
6	Correct	0 ms	16840 KB	Output is correct
7	Correct	0 ms	16840 KB	Output is correct
8	Incorrect	0 ms	16840 KB	Output isn't correct
9	Incorrect	0 ms	16840 KB	Output isn't correct
10	Incorrect	0 ms	16840 KB	Output isn't correct
11	Correct	20 ms	17612 KB	Output is correct
12	Correct	16 ms	16840 KB	Output is correct
13	Incorrect	170 ms	16840 KB	Output isn't correct
14	Incorrect	180 ms	16840 KB	Output isn't correct
15	Incorrect	147 ms	16840 KB	Output isn't correct
16	Incorrect	155 ms	16840 KB	Output isn't correct
17	Incorrect	183 ms	16840 KB	Output isn't correct
18	Incorrect	209 ms	16840 KB	Output isn't correct
19	Incorrect	183 ms	16840 KB	Output isn't correct
20	Correct	135 ms	16840 KB	Output is correct