Submission #13631

#	Time	Username	Problem	Language	Result	Execution time	Memory
13631		gs14004	Mountain Trek Route (IZhO12_route)	C++14	95 / 100	228 ms	13548 KiB

route

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

int n,k,a[1000005];
int cost[1000005];

stack<int> s,t;

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);
    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 ptop = s.top();
                s.pop();
                t.pop();
                cost[i - t.top() - 1] += min(s.top(),a[i%n]) - ptop;
            }
            s.push(a[i%n]);
            t.push(i);
        }
    }
    int ret = 0;
    for (int i=1; i<=n && i<=k; i++) {
        int change = min(cost[i],k/i);
        ret += change * 2;
        k -= change * i;
    }
    printf("%d",ret);
}

• Subtask 1: 95 / 100