Submission #12245

#	Time	Username	Problem	Language	Result	Execution time	Memory
12245		pro0331	격자 보존하기 (GA9_preserve)	C++98	100 / 100	28 ms	1476 KiB

preserve

#include <stdio.h>
#include <algorithm>
#include <functional>

int n, k, d, blank[100001];

int main()
{
	int i, p;
	int last = 0;
	scanf("%d %d %d", &n, &k, &d);
	for (i = 0; i < k; i++) {
		scanf("%d", &p);
		blank[i] = p - last - 1;
		last = p;
	}
	blank[k] = n - last;

	int first = blank[0];
	last = blank[k];
	sort(blank, blank+k+1, std::greater<int>());

	int result = 0;
	for (i = 0; d > 1 && i <= k; i++) {
		result += blank[i];
		if (first == blank[i]) {
			first = 0;
			d--;
		} else if (last == blank[i]) {
			last = 0;
			d--;
		} else {
			d -= 2;
		}
	}
	if (d == 1)
		result += std::max(first, last);
	else if (first + last > blank[i-1])
		result = result - blank[i-1] + first + last;
	printf("%d\n", result);
}

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