Submission #12667

#	Time	Username	Problem	Language	Result	Execution time	Memory
12667		kipa00	격자 보존하기 (GA9_preserve)	C++98	0 / 100	36 ms	2372 KiB

preserve

#include <cstdio>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<int> > put;
int horse[100000];

int main() {
    int start, end, n, k, d;
    int i;
    scanf("%d %d %d", &n, &k, &d);
    for (i=0; i<k; ++i) {
        scanf("%d", &horse[i]);
    }
    start = horse[0] - 1;
    end = n - horse[k - 1];
    for (i=1; i<k; ++i) {
        put.push(horse[i] - horse[i - 1] - 1);
    }
    if (d == 1) printf("%d\n", (start > end) ? start : end);
    else if (d == 2) printf("%d\n", (start + end > put.top()) ? (start + end) : put.top());
    else {
        int now = 0;
        while (d >= 0) {
            int max = start, cost = 1, *ptr = &start;
            if (max < end) {
                max = end;
                ptr = &end;
            }
            if (max < put.top()) {
                max = put.top();
                ptr = 0;
                cost = 2;
            }
            if (d < cost) break;
            d -= cost;
            now += max;
            if (!ptr) {
                put.pop();
            } else *ptr = -1;
        }
        printf("%d\n", now);
    }
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 17
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 35