1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <bits/stdc++.h>
using namespace std;
const int MAX_SUM = 5e5;
int t[2][MAX_SUM * 2 + 10];
int H[2003];
uint8_t eligible[2][MAX_SUM * 2 + 10]; // 0 - not used, 1 - only st, 2 - only nd, 3 - both
int main() {
int n, sum = 0, which = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &H[i]);
sort(H, H + n);
for (int i = 0; i < n; i++) {
// cout << i << "\n";
int h = H[i], *prev = t[which], *cur = t[which ^ 1];
uint8_t *pe = eligible[which], *ce = eligible[which ^ 1];
for (int dif = -sum; dif <= sum; ++dif) {
int aux = 0;
// cout << (int)pe[dif + MAX_SUM] << "\n";
if (abs(dif) > MAX_SUM || (pe[dif + MAX_SUM] == 0 && dif != 0)) continue;
if (dif + h <= MAX_SUM) {
if (dif >= 0) {
aux = h;
} else if (dif + h > 0) {
aux = dif + h;
}
int idx = dif + h + MAX_SUM;
cur[idx] = max({cur[idx], prev[idx], prev[idx - h] + aux});
ce[idx] |= pe[dif + MAX_SUM] | 1;
// cout << "> " << idx - MAX_SUM << " " << cur[idx] << " " << (int)eligible[idx] << "\n";
}
if (dif - h >= -MAX_SUM) {
aux = 0;
if (dif <= 0) {
aux = h;
} else if (dif - h < 0) {
aux = h - dif;
}
int idx = dif - h + MAX_SUM;
cur[idx] = max({cur[idx], prev[idx], prev[idx + h] + aux});
ce[idx] |= pe[dif + MAX_SUM] | 2;
// cout << ">> " << idx - MAX_SUM << " " << cur[idx] << " " << (int)eligible[idx] << "\n";
}
}
sum += h;
which ^= 1;
// for (int dif = -sum; dif <= sum; ++dif) {
// cout << dif << " " << " " << (int)ce[dif + MAX_SUM] << " " << cur[dif + MAX_SUM] << "\n";
// }
// printf("-----\n");
}
if (eligible[which][MAX_SUM] == 3) {
printf("TAK\n%d\n", t[which][MAX_SUM]);
} else {
int mini = 1e9;
for (int i = -MAX_SUM; i <= MAX_SUM; i++) {
if (eligible[which][i + MAX_SUM] == 3)
mini = min(mini, abs(i));
}
printf("NIE\n%d\n", mini);
}
}
|
