# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
244836 |
2020-07-05T07:09:17 Z |
NONAME |
Kas (COCI17_kas) |
C++14 |
|
2000 ms |
142872 KB |
#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], total;
map <int, int> f[500];
map <int, bool> mk[500];
int rec(int p, int cur) {
if (p == n)
return (cur == 0) ? 0 : -3e5;
if (mk[p][int(1e5) + cur])
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]));
mk[p][int(1e5) + cur] = 1;
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";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
640 KB |
Output is correct |
2 |
Correct |
6 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
512 KB |
Output is correct |
2 |
Correct |
7 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
640 KB |
Output is correct |
2 |
Correct |
8 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
768 KB |
Output is correct |
2 |
Correct |
7 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
1152 KB |
Output is correct |
2 |
Correct |
10 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
2560 KB |
Output is correct |
2 |
Correct |
21 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
5120 KB |
Output is correct |
2 |
Correct |
20 ms |
2560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2096 ms |
142872 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2094 ms |
140944 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2090 ms |
138344 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |