답안 #16901

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16901	2015-10-24T14:22:31 Z	erdemkiraz	등산 경로 (IZhO12_route)	C++	50 / 100	2000 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++) {
        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;
        }
        assert(p);
        flag = 1;
        k -= p * len;
        ans += p * 2;
        s.erase(s.begin());
    }

    cnt++;

}

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

    return 0;

}

Subtask #1

50.0 / 100.0

#	결과	실행 시간	메모리	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	521 ms	9536 KB	Output is correct
11	Correct	29 ms	11516 KB	Output is correct
12	Correct	74 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	390 ms	9536 KB	Output isn't correct