Submission #13364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13364	2015-02-13T17:32:07 Z	baneling100	Mountain Trek Route (IZhO12_route)	C++	45 / 100	240 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 {
                inp=Size[Left[t2]];
                Size [Left[t2]]+=Size[t2]+Size[Right[t2]];
                Right[Left[t2]] =Right[Right[t2]];
                Size[Right[t2]]+=Size[t2]+inp;
                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

45.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	Correct	0 ms	16840 KB	Output is 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	23 ms	16840 KB	Output isn't correct
11	Correct	16 ms	17612 KB	Output is correct
12	Correct	16 ms	16840 KB	Output is correct
13	Incorrect	155 ms	16840 KB	Output isn't correct
14	Incorrect	169 ms	16840 KB	Output isn't correct
15	Incorrect	163 ms	16840 KB	Output isn't correct
16	Incorrect	226 ms	16840 KB	Output isn't correct
17	Incorrect	156 ms	16840 KB	Output isn't correct
18	Incorrect	166 ms	16840 KB	Output isn't correct
19	Incorrect	240 ms	16840 KB	Output isn't correct
20	Correct	133 ms	16840 KB	Output is correct