Submission #13630

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

route

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

• Subtask 1: 95 / 100