이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl
using namespace std;
typedef long long ll;
const int N = 505 , M = 1e5 + 4;
int n , memo[N][M];
vector<int> a;
int solve(int indx , int s){
if(indx == n){
return (!s ? 0 : -inf);
}
int &ret = memo[indx][s];
if(~ret)
return ret;
ret = -inf;
ret = max(ret , 1 + solve(indx + 1 , s + a[indx]));
ret = max(ret , 1 + solve(indx + 1 , abs(s - a[indx])));
ret = max(ret , solve(indx + 1 , s));
return ret;
}
int v , sum = 0;
void path(int indx , int s){
if(indx == n){
return;
}
int mx = solve(indx , s);
if(1 + solve(indx + 1 , s + a[indx]) == mx){
sum += a[indx];
path(indx + 1 , s + a[indx]);
}
else if(1 + solve(indx + 1 , abs(s - a[indx])) == mx){
sum += a[indx];
path(indx + 1 , s - a[indx]);
}
else{
path(indx + 1 , s);
}
}
int main() {
ios::sync_with_stdio() , cin.tie(0) , cin.tie(0);
int tot = 0;
cin >> n;
a.resize(n);
for(int &x : a)
cin >> x , tot += x;
memset(memo , -1 , sizeof memo);
v = solve(0 , 0);
path(0 , 0);
sum /= 2;
cout << sum + (tot - 2 * sum) << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |