제출 #13363

#제출 시각아이디문제언어결과실행 시간메모리
13363baneling100등산 경로 (IZhO12_route)C++98
40 / 100
209 ms17612 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...