제출 #13629

#제출 시각아이디문제언어결과실행 시간메모리
13629gs14004등산 경로 (IZhO12_route)C++14
25 / 100
1412 ms13548 KiB
#include <cstdio> #include <algorithm> #include <stack> #include <queue> #include <utility> using namespace std; int n,k,a[1000005]; int cost[1000005]; int main(){ scanf("%d %d",&n,&k); for (int i=0; i<n; i++) { scanf("%d",&a[i]); } int p = (int)(max_element(a,a+n) - a); stack<int> s,t; for (int i=p; i<=p+n; i++) { if(s.empty() || s.top() >= a[i%n]){ s.push(a[i%n]); t.push(i); } else{ while (!s.empty() && s.top() < a[i%n]) { int val = 0, ptop = s.top(); s.pop(); if(!s.empty() && s.top() < a[i%n]){ val = s.top() - ptop; } else{ val = a[i%n] - ptop; } cost[i - t.top()] += val; t.pop(); } s.push(a[i%n]); t.push(i); } } int ret = 0; for (int i=1; i<=n; i++) { while (cost[i] && k >= i) { ret += 2; k -= i; cost[i]--; } } printf("%d",ret); }
#Verdict Execution timeMemoryGrader output
Fetching results...