Submission #16900

#	Time	Username	Problem	Language	Result	Execution time	Memory
16900		erdemkiraz	Mountain Trek Route (IZhO12_route)	C++98	50 / 100	2000 ms	11516 KiB

route

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 2e6 + 5;

int n, k, ans;
int a[N];

int main() {

    scanf("%d %d", &n, &k);

    for(int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }

    for(int i = 0; i < n; i++) {
        int l = (i + n - 1) % n;
        int r = (i + 1) % n;
        int dif = min(a[l], a[r]) - a[i];
        if(dif >= 0) {
            dif = min(dif, k);
            k -= dif;
            ans += 2 * dif;
            a[i] += dif;
        }
    }

bool flag = 1;
int cnt = 0;

while(flag) {

    for(int i = 0; i < n; i++)
        a[i + n] = a[i];

    flag = 0;

    set < pair < int, ii > > s;

    for(int i = 0; i < n; i++) {
        int j = i;
        while(j + 1 < 2 * n and a[j + 1] == a[i])
            j++;
        if(!i and a[n - 1] == a[0]) {
            i = j;
            continue;
        }
        int l = (i + n - 1) % n;
        int r = (j + 1) % n;
        if(a[i] < a[l] and a[i] < a[r]) {
            s.insert(make_pair(j - i + 1, ii(i, j)));
        }
        i = j;
    }

    while(s.size()) {
        int len = s.begin() -> first;
        int i = s.begin() -> second.first;
        int j = s.begin() -> second.second;
        int l = (i + n - 1) % n;
        int r = (j + 1) % n;
        if(k < len) {
            break;
        }
        int p = min(k / len, min(a[l], a[r]) - a[i]);
        for(; i <= j; i++) {
            a[i % n] += p;
        }
        flag |= (bool) p;
        k -= p * len;
        ans += p * 2;
        s.erase(s.begin());
    }

    cnt++;

}

    printf("%d\n", ans);

    return 0;

}

• Subtask 1: 50 / 100