oj.uz

답안 #20131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20131 2016-02-27T12:29:57 Z hongjun7 격자 보존하기 (GA9_preserve) C++14
61 / 100
 167 ms 2892 KB 
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXK 100000
int n, k, d, p[MAXK + 1];
struct BLOCK {
	int cost, value;
} b[MAXK + 5]; int bn;
inline bool cmp(BLOCK b1, BLOCK b2) {
	if (b1.value != b2.value) return b1.value > b2.value;
	return b1.cost < b2.cost;
}
inline bool cmp2(BLOCK b1, BLOCK b2) {
	if (b1.value != b2.value) return b1.value > b2.value;
	return b1.cost > b2.cost;
}
int res;
void solve() {
	int sum = 0, D = d;
	for (int i = 1; i <= bn; i++) {
		if (b[i].cost <= D) {
			D -= b[i].cost;
			sum += b[i].value;
		}
	}
	if (res < sum) res = sum;
}
int main() {
	cin >> n >> k >> d;
	for (int i = 1; i <= k; i++) cin >> p[i];
	bn = 0; b[++bn] = { 1, p[1] - 1 }; b[++bn] = { 1, n - p[k] };
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp); solve();
	bn = 0; b[++bn] = { 1, p[1] - 1 };
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp); solve();
	bn = 0; b[++bn] = { 1, n - p[k] };
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp); solve();
	bn = 0;
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp); solve();
	bn = 0; b[++bn] = { 1, p[1] - 1 }; b[++bn] = { 1, n - p[k] };
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp2); solve();
	bn = 0; b[++bn] = { 1, p[1] - 1 };
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp2); solve();
	bn = 0; b[++bn] = { 1, n - p[k] };
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp2); solve();
	bn = 0;
	for (int i = 2; i <= k; i++) b[++bn] = { 2, p[i] - p[i - 1] - 1 };
	sort(b + 1, b + bn + 1, cmp2); solve();
	cout << res;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2892 KB Output is correct
2 Correct 0 ms 2892 KB Output is correct
3 Correct 0 ms 2892 KB Output is correct
4 Correct 0 ms 2892 KB Output is correct
5 Correct 0 ms 2892 KB Output is correct
6 Correct 0 ms 2892 KB Output is correct
7 Correct 0 ms 2892 KB Output is correct
8 Correct 0 ms 2892 KB Output is correct
9 Correct 0 ms 2892 KB Output is correct
10 Correct 0 ms 2892 KB Output is correct
11 Correct 0 ms 2892 KB Output is correct
12 Correct 0 ms 2892 KB Output is correct
13 Correct 0 ms 2892 KB Output is correct
14 Correct 0 ms 2892 KB Output is correct
15 Correct 0 ms 2892 KB Output is correct
16 Correct 0 ms 2892 KB Output is correct
17 Correct 0 ms 2892 KB Output is correct
18 Correct 0 ms 2892 KB Output is correct
19 Correct 0 ms 2892 KB Output is correct
20 Correct 0 ms 2892 KB Output is correct
21 Correct 0 ms 2892 KB Output is correct
22 Correct 0 ms 2892 KB Output is correct
23 Correct 0 ms 2892 KB Output is correct
24 Correct 0 ms 2892 KB Output is correct
25 Correct 0 ms 2892 KB Output is correct
26 Correct 0 ms 2892 KB Output is correct
27 Correct 0 ms 2892 KB Output is correct
28 Correct 0 ms 2892 KB Output is correct
29 Correct 0 ms 2892 KB Output is correct
30 Correct 0 ms 2892 KB Output is correct
31 Correct 0 ms 2892 KB Output is correct
32 Correct 0 ms 2892 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2892 KB Output is correct
2 Correct 0 ms 2892 KB Output is correct
3 Correct 0 ms 2892 KB Output is correct
4 Correct 0 ms 2892 KB Output is correct
5 Correct 0 ms 2892 KB Output is correct
6 Correct 0 ms 2892 KB Output is correct
7 Correct 0 ms 2892 KB Output is correct
8 Correct 0 ms 2892 KB Output is correct
9 Correct 0 ms 2892 KB Output is correct
10 Correct 0 ms 2892 KB Output is correct
11 Correct 0 ms 2892 KB Output is correct
12 Correct 0 ms 2892 KB Output is correct
13 Correct 0 ms 2892 KB Output is correct
14 Correct 0 ms 2892 KB Output is correct
15 Correct 0 ms 2892 KB Output is correct
16 Correct 0 ms 2892 KB Output is correct
17 Correct 0 ms 2892 KB Output is correct
18 Correct 0 ms 2892 KB Output is correct
19 Correct 0 ms 2892 KB Output is correct
20 Correct 0 ms 2892 KB Output is correct
21 Correct 0 ms 2892 KB Output is correct
22 Correct 0 ms 2892 KB Output is correct
23 Correct 0 ms 2892 KB Output is correct

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2892 KB Output is correct
2 Correct 0 ms 2892 KB Output is correct
3 Correct 0 ms 2892 KB Output is correct
4 Correct 2 ms 2892 KB Output is correct
5 Correct 1 ms 2892 KB Output is correct
6 Correct 0 ms 2892 KB Output is correct
7 Correct 1 ms 2892 KB Output is correct
8 Correct 0 ms 2892 KB Output is correct
9 Correct 0 ms 2892 KB Output is correct
10 Incorrect 0 ms 2892 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 2892 KB Output is correct
2 Correct 149 ms 2892 KB Output is correct
3 Correct 154 ms 2892 KB Output is correct
4 Correct 164 ms 2892 KB Output is correct
5 Correct 155 ms 2892 KB Output is correct
6 Correct 163 ms 2892 KB Output is correct
7 Correct 144 ms 2892 KB Output is correct
8 Correct 149 ms 2892 KB Output is correct
9 Incorrect 71 ms 2892 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 2892 KB Output is correct
2 Correct 160 ms 2892 KB Output is correct
3 Correct 151 ms 2892 KB Output is correct
4 Correct 153 ms 2892 KB Output is correct
5 Correct 138 ms 2892 KB Output is correct
6 Correct 164 ms 2892 KB Output is correct
7 Correct 158 ms 2892 KB Output is correct
8 Correct 167 ms 2892 KB Output is correct
9 Correct 76 ms 2892 KB Output is correct
10 Correct 49 ms 2892 KB Output is correct
11 Correct 102 ms 2892 KB Output is correct
12 Correct 98 ms 2892 KB Output is correct
13 Correct 118 ms 2892 KB Output is correct
14 Correct 118 ms 2892 KB Output is correct
15 Correct 106 ms 2892 KB Output is correct
16 Correct 128 ms 2892 KB Output is correct
17 Correct 152 ms 2892 KB Output is correct
18 Correct 119 ms 2892 KB Output is correct
19 Correct 122 ms 2892 KB Output is correct
20 Correct 149 ms 2892 KB Output is correct