#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
const int fx = -(3e5 + 100);
int n, a[500], f[500][int(3e5) + 10], total;
int rec(int p, int cur) {
if (p == n)
return (cur == 0) ? 0 : -3e5;
if (f[p][int(1e5) + cur] != fx)
return f[p][int(1e5) + cur];
int res = max(rec(p + 1, cur),
max(rec(p + 1, cur - a[p]), rec(p + 1, cur + a[p]) + a[p]));
return f[p][int(1e5) + cur] = res;
}
int main() {
fast_io;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
total += a[i];
}
for (int i = 0; i < n; ++i)
for (int j = 0; j <= 3e5; ++j)
f[i][j] = fx;
int res = rec(0, 0);
cout << res + (total - 2 * res) << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12032 KB |
Output is correct |
2 |
Correct |
13 ms |
12032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
12032 KB |
Output is correct |
2 |
Correct |
15 ms |
12032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
12032 KB |
Output is correct |
2 |
Correct |
13 ms |
13312 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
14464 KB |
Output is correct |
2 |
Correct |
16 ms |
15616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
15616 KB |
Output is correct |
2 |
Correct |
15 ms |
15616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
41472 KB |
Output is correct |
2 |
Correct |
37 ms |
47352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
53112 KB |
Output is correct |
2 |
Correct |
44 ms |
59084 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
268 ms |
235168 KB |
Output is correct |
2 |
Correct |
223 ms |
293880 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
385 ms |
352632 KB |
Output is correct |
2 |
Correct |
487 ms |
470136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
325 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |