Submission #13627

#	Time	Username	Problem	Language	Result	Execution time	Memory
13627		gs14004	Mountain Trek Route (IZhO12_route)	C++14	15 / 100	266 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 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();
            }
        }
    }
    int ret = 0;
    for (int i=1; i<=n; i++) {
        int diff = min(k/i * i,cost[i] * i);
        k -= diff;
        ret += diff / i * 2;
    }
    printf("%d",ret);
}

• Subtask 1: 15 / 100