답안 #16903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16903	2015-10-24T16:41:44 Z	erdemkiraz	등산 경로 (IZhO12_route)	C++	20 / 100	229 ms	41844 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] = i;

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

    set < ii > s;

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

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

    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) % n)];
        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);
        }
        x = f(x);
        i = beg[x];
        j = end[x];
        l = val[f(i - 1)];
        r = val[f((j + 1) % n)];
        if(val[x] < l and val[x] < r) {
            s.insert(ii(j - i + 1, x));
        }
    }

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

    return 0;

}

Subtask #1

20.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	Incorrect	0 ms	40788 KB	Output isn't correct
6	Incorrect	0 ms	40788 KB	Output isn't correct
7	Incorrect	0 ms	40788 KB	Output isn't correct
8	Incorrect	0 ms	40788 KB	Output isn't correct
9	Incorrect	0 ms	40788 KB	Output isn't correct
10	Incorrect	17 ms	40788 KB	Output isn't correct
11	Correct	23 ms	41844 KB	Output is correct
12	Incorrect	15 ms	40788 KB	Output isn't correct
13	Incorrect	189 ms	40788 KB	Output isn't correct
14	Incorrect	197 ms	40788 KB	Output isn't correct
15	Incorrect	150 ms	40788 KB	Output isn't correct
16	Incorrect	138 ms	40788 KB	Output isn't correct
17	Incorrect	229 ms	40788 KB	Output isn't correct
18	Incorrect	198 ms	40788 KB	Output isn't correct
19	Incorrect	180 ms	40788 KB	Output isn't correct
20	Incorrect	167 ms	40788 KB	Output isn't correct