This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505 ;
const int MAXSUM = 100010 ;
const int CONS = 100000 ;
int arr[MAXN] ;
int dp[MAXN][MAXSUM+CONS] ;
int n ;
int solve(int idx , int diff)
{
if(idx == n)
{
if(diff - CONS == 0)
return 0 ;
return -1e8 ;
}
int &ret = dp[idx][diff] ;
if(ret != -1)
return ret ;
ret = solve(idx+1 , diff) ;
ret = max(ret , solve(idx+1 , diff + arr[idx]) + arr[idx]) ;
ret = max(ret , solve(idx+1 , diff - arr[idx]) + arr[idx]) ;
return ret ;
}
int main()
{
memset(dp , -1 , sizeof(dp)) ;
cin>>n ;
int sum = 0 ;
for(int i = 0 ; i < n ; ++i)
{
cin>>arr[i] ;
sum += arr[i] ;
}
int ans = solve(0 , CONS) ;
//debugging
if(ans & 1)
while(1) ;
return cout<<ans/2+sum-ans<<"\n" , 0 ;
}
# | 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... |