#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ordered_set <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset <int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define f first
#define s second
#define emb emplace_back
#define emf emplace_front
#define em emplace
#define all(x) x.begin(),x.end()
#define DB cout<<"\n";system("pause");
#define sp <<" "<<
#define inf (int)(1e9)
#define INF (ll)(1e18)
#define mod (int)(1e9 + 7)
#define maxn 55
int n,max_sum , sum;
int vec[maxn];
void way(int ind , int sum1 , int sum2){
if(ind == n+1){
if(sum1 == sum2){
max_sum = max(max_sum , sum1);
}
return ;
}
way(ind + 1 , sum1 + vec[ind] , sum2);
way(ind + 1 , sum1 , sum2 + vec[ind]);
way(ind + 1 , sum1 , sum2);
}
int mem[maxn][1001][1001];
bool solve2(int pos,int sum1 , int sum2){
if(sum1 == 0 && sum2 == 0)return true;
if(pos >= n + 1)return false;
else if(sum1 < 0 || sum2 < 0)return false;
else if(mem[pos][sum1][sum2] != -1)return mem[pos][sum1][sum2];
return mem[pos][sum1][sum2] = solve2(pos + 1 , sum1 - vec[pos] , sum2) ||
solve2(pos + 1 , sum1 , sum2 - vec[pos]) ||
solve2(pos + 1 , sum1 , sum2);
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>vec[i];
sum += vec[i];
}
if(n <= 13){
way(1,0,0);
cout<<max_sum + (sum - max_sum * 2);
return 0;
}
else {
memset(mem,-1,sizeof(mem));
// cout<<solve2(1,13,13);
for(int i=sum / 2; i >= 0 ; i--){
if(solve2(1,i,i)){
cout<< i + (sum - 2*i);
return 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... |