Submission #1196388

#TimeUsernameProblemLanguageResultExecution timeMemory
1196388flukeKas (COCI17_kas)C++20
70 / 100
201 ms216244 KiB
#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 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...