답안 #13369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13369	2015-02-13T17:57:46 Z	baneling100	등산 경로 (IZhO12_route)	C++	100 / 100	237 ms	17612 KB

route

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define N_MAX 1000000
#include <stdlib.h>
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);
    Block[0]=-1;
    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

100.0 / 100.0

#	결과	실행 시간	메모리	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	Correct	0 ms	16840 KB	Output is correct
6	Correct	1 ms	16840 KB	Output is correct
7	Correct	0 ms	16840 KB	Output is correct
8	Correct	0 ms	16840 KB	Output is correct
9	Correct	0 ms	16840 KB	Output is correct
10	Correct	18 ms	16840 KB	Output is correct
11	Correct	15 ms	17612 KB	Output is correct
12	Correct	21 ms	16840 KB	Output is correct
13	Correct	76 ms	16840 KB	Output is correct
14	Correct	178 ms	16840 KB	Output is correct
15	Correct	150 ms	16840 KB	Output is correct
16	Correct	147 ms	16840 KB	Output is correct
17	Correct	147 ms	16840 KB	Output is correct
18	Correct	237 ms	16840 KB	Output is correct
19	Correct	161 ms	16840 KB	Output is correct
20	Correct	107 ms	16840 KB	Output is correct