oj.uz

Submission #16899

# Submission time Handle Problem Language Result Execution time Memory
16899 2015-10-24T14:19:05 Z erdemkiraz Mountain Trek Route (IZhO12_route) C++
50 / 100
 2000 ms 11516 KB 
#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);
    }

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9536 KB Output is correct
2 Correct 0 ms 9536 KB Output is correct
3 Correct 0 ms 9536 KB Output is correct
4 Correct 0 ms 9536 KB Output is correct
5 Correct 0 ms 9536 KB Output is correct
6 Incorrect 0 ms 9536 KB Output isn't correct
7 Incorrect 0 ms 9536 KB Output isn't correct
8 Correct 0 ms 9536 KB Output is correct
9 Correct 0 ms 9536 KB Output is correct
10 Correct 532 ms 9536 KB Output is correct
11 Correct 34 ms 11516 KB Output is correct
12 Correct 79 ms 9536 KB Output is correct
13 Execution timed out 2000 ms 9532 KB Program timed out
14 Execution timed out 2000 ms 9532 KB Program timed out
15 Execution timed out 2000 ms 9532 KB Program timed out
16 Execution timed out 2000 ms 9532 KB Program timed out
17 Execution timed out 2000 ms 9532 KB Program timed out
18 Execution timed out 2000 ms 9532 KB Program timed out
19 Execution timed out 2000 ms 9532 KB Program timed out
20 Incorrect 394 ms 9536 KB Output isn't correct