Submission #16898

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
16898	2015-10-24T14:18:14 Z	erdemkiraz	Mountain Trek Route (IZhO12_route)	C++	15 / 100	236 ms	11516 KB

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++)
        a[i + n] = a[i];

bool flag = 1;
int cnt = 0;

while(flag) {

    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++;

    if(cnt > 5)
        break;

}

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

    return 0;

}

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9536 KB	Output is correct
2	Incorrect	0 ms	9536 KB	Output isn't correct
3	Incorrect	0 ms	9536 KB	Output isn't correct
4	Correct	0 ms	9536 KB	Output is correct
5	Incorrect	0 ms	9536 KB	Output isn't correct
6	Incorrect	0 ms	9536 KB	Output isn't correct
7	Incorrect	0 ms	9536 KB	Output isn't correct
8	Incorrect	0 ms	9536 KB	Output isn't correct
9	Incorrect	0 ms	9536 KB	Output isn't correct
10	Incorrect	17 ms	9536 KB	Output isn't correct
11	Correct	44 ms	11516 KB	Output is correct
12	Incorrect	18 ms	9536 KB	Output isn't correct
13	Incorrect	236 ms	9536 KB	Output isn't correct
14	Incorrect	209 ms	9536 KB	Output isn't correct
15	Incorrect	201 ms	9536 KB	Output isn't correct
16	Incorrect	209 ms	9536 KB	Output isn't correct
17	Incorrect	219 ms	9536 KB	Output isn't correct
18	Incorrect	218 ms	9536 KB	Output isn't correct
19	Incorrect	148 ms	9536 KB	Output isn't correct
20	Incorrect	158 ms	9536 KB	Output isn't correct