제출 #244837

#제출 시각아이디문제언어결과실행 시간메모리
244837NONAMEKas (COCI17_kas)C++14
70 / 100
2102 ms154552 KiB
#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; bool mk[500][int(3e5) + 10]; map <int, int> f[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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...