답안 #16906

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16906	2015-10-24T16:48:40 Z	erdemkiraz	등산 경로 (IZhO12_route)	C++	95 / 100	183 ms	42240 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++)
#define end ____end

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], root[N], beg[N], end[N], val[N];

int f(int x) {
    if(x == root[x])
        return x;
    return root[x] = f(root[x]);
}

void merge(int x, int y) {
    x = f(x);
    y = f(y);
    if(val[x] != val[y])
        return;
    root[y] = x;
    beg[x] = min(beg[x], beg[y]);
    end[x] = max(end[x], end[y]);
}

int main() {

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

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

    int ind = max_element(a, a + n) - a;

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

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

    set < ii > s;

    val[0] = a[0];
    root[n] = 0;

    for(int i = 1; i < n; i++) {
        int j = i;
        while(j + 1 < n and a[j + 1] == a[i])
            j++;
        for(int k = i; k <= j; k++)
            root[k] = i;
        val[i] = a[i];
        beg[i] = i;
        end[i] = j;
        int l = i - 1;
        int r = (i + 1) % n;
        if(a[i] < a[l] and a[i] < a[r]) {
            s.insert(ii(j - i + 1, i));
        }
        i = j;
    }

    while(s.size()) {
        int len = s.begin() -> first;
        if(k < len)
            break;
        int x = s.begin() -> second;
        s.erase(s.begin());
        int i = beg[x];
        int j = end[x];
        int l = val[f(i - 1)];
        int r = val[f(j + 1)];
        int p = min(k / len, min(l, r) - val[x]);
        k -= p * len;
        ans += p * 2;
        val[x] += p;
        if(i - 1 > 0) {
            merge(x, i - 1);
        }
        if(j + 1 < n) {
            merge(x, j + 1);
        }
        i = beg[x];
        j = end[x];
        l = val[f(i - 1)];
        r = val[f(j + 1)];
        if(val[x] < l and val[x] < r) {
            s.insert(ii(j - i + 1, x));
        }
    }

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

    return 0;

}

Subtask #1

95.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	40788 KB	Output is correct
2	Incorrect	0 ms	40788 KB	Output isn't correct
3	Correct	0 ms	40788 KB	Output is correct
4	Correct	0 ms	40788 KB	Output is correct
5	Correct	0 ms	40788 KB	Output is correct
6	Correct	0 ms	40788 KB	Output is correct
7	Correct	0 ms	40788 KB	Output is correct
8	Correct	0 ms	40788 KB	Output is correct
9	Correct	0 ms	40788 KB	Output is correct
10	Correct	0 ms	40788 KB	Output is correct
11	Correct	21 ms	42240 KB	Output is correct
12	Correct	12 ms	40788 KB	Output is correct
13	Correct	170 ms	40788 KB	Output is correct
14	Correct	170 ms	40788 KB	Output is correct
15	Correct	149 ms	40788 KB	Output is correct
16	Correct	132 ms	40788 KB	Output is correct
17	Correct	139 ms	40788 KB	Output is correct
18	Correct	177 ms	40788 KB	Output is correct
19	Correct	183 ms	40788 KB	Output is correct
20	Correct	118 ms	40788 KB	Output is correct