fork download
copy 
  1. // Problem: B. Fair Division
  2. // Contest: Codeforces - Codeforces Round 693 (Div. 3)
  3. // URL: https://c...content-available-to-author-only...s.com/problemset/problem/1472/B
  4. // Memory Limit: 256 MB
  5. // Time Limit: 2000 ms
  6. // 
  7. // Powered by CP Editor (https://c...content-available-to-author-only...r.org)
  8.  
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11.  
  12. bool multicases_=true;
  13.  
  14. #include <ext/pb_ds/assoc_container.hpp>
  15. #include <ext/pb_ds/tree_policy.hpp>
  16. using namespace __gnu_pbds;
  17. // template<class  T>using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
  18. template<typename T>using ordered_multiset = tree<pair<T, int>, null_type, less<pair<T, int>>, rb_tree_tag, tree_order_statistics_node_update>;
  19. template<typename T>using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  20.  
  21. using ll = long long;
  22. #define int long long//<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<??
  23. typedef unsigned long long u64;//this or the one  below
  24. #define ull unsigned long long
  25.  
  26.  
  27.  
  28. int total,n;
  29. vector<int>v;
  30.  
  31. // int dp[105][205];
  32.  
  33.  
  34.  
  35. // bool go(int idx,int taken){
  36. // 	
  37. 	// if(taken*2==total)return true;
  38. // 	
  39. 	// //fix : >n-1 not >n
  40. 	// if(idx>n-1||taken>total)return false;
  41. // 	
  42. 	// if(~dp[idx][taken])return dp[idx][taken];
  43. // 	
  44. 	// bool ch1= go(idx+1,taken+v[idx]);
  45. 	// bool ch2= go(idx+1,taken);
  46. // 	
  47. 	// bool ans=ch1||ch2;
  48. // 	
  49. 	// return dp[idx][taken]=ans; // fixxx  :  dp=ans not vice versa !!!!
  50. // }
  51.  
  52. void pre_compute(){
  53. 	//fix: reset each time not only here
  54.  
  55. 	///this was wrong order in the memset function:
  56. 	// memset(dp,sizeof(dp),-1);
  57. }
  58.  
  59. void solve(int tc){
  60. 	// //dbg:
  61. 	 // cerr<<"at the test case no."<<tc<<" : \n";
  62.  
  63. 	//you can use instead of that number of indices left 
  64. 									//and initalize only before the first test case
  65. 	// memset(dp, -1, sizeof(dp));
  66.  
  67. 	cin>>n;
  68. 	v.assign(n,0);
  69. 	for(auto&x:v)cin>>x;
  70. 	total=accumulate(v.begin(),v.end(),0LL);
  71.  
  72.  
  73. 	// cout<<(go(0,0)?"YES\n":"NO\n");
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88. 	//iterative dp now:
  89.  
  90. 	//if total is not divisible by 2 then immediately reurn the output NO\n 
  91. 	if (total % 2) {
  92.         cout << "NO\n";
  93.         return;
  94.     }
  95.  
  96.  
  97. 	int target=total/2;//focus error fix:total/2 not n/2
  98. 	vector<vector<bool>>dp(n+1,vector<bool>(target+1,false));
  99.  
  100. 	//states : dp[i][s] => i means how many candies are we allowed to use
  101. 	//					=> s means what sum are we trying to make
  102.  
  103.  
  104. 	//base case: we can build sum of 0 using 0 candies
  105. 	dp[0][0]=true;
  106. 	//all s values for i=1 is false
  107. 		//because when you don't choose anything all what you can make is 1
  108.  
  109.  
  110. 	for(int i = 1 ;i <= n ;i++){	//you have now i elements to build your target
  111.  
  112. 		for(int s = 0; s<=target;s++){	//know if s is reachable from the i indices
  113. 												//may be some of them 
  114.  
  115. 			//leave
  116. 			//if i can make s without the current candy 
  117. 				//then it can be done with the current candy also
  118. 			dp[i][s]=dp[i-1][s];
  119.  
  120.  
  121. 			//take
  122. 			//if i take the current one, can the previous ones build the remaining ?
  123. 			if(s>=v[i-1]){
  124. 				dp[i][s]=dp[i][s]||dp[i-1][s-v[i-1]];
  125. 			}
  126.  
  127. 		}
  128.  
  129. 	}
  130.  
  131.  
  132. 	//now the question is can i build the target from the n elements
  133. 						// and the target is total/2
  134. 	// so if we can build the half of the sum from the n elements
  135. 				//then the reamining half is the rest untaken cells
  136. 	cout<<(dp[n][target]?"YES\n":"NO\n");
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151. 	// int ones=count(v.begin(),v.end(),1),twos=count(v.begin(),v.end(),2);
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160. // 	
  161. 	// int sm=ones+twos*2;
  162. // 	
  163. 	// //summation of all values must be even
  164. 	// if(sm&1) return void (cout<<"NO\n");
  165. // 	
  166. 	// //if total is even and we have someones so these ones summation must be even
  167. 			// //becuase twos are actually even so also ones summation is even
  168. 										// //to make the total sum even
  169. // 	
  170. 	// //if we have ones (and as proved summation of ones is even)
  171. 	// if(ones)return void (cout<<"YES\n"); 
  172. // 	
  173. // 	
  174. 	// //examples
  175. 	// // 	when number of twos is even : 2 2 1 1     (2 1 , 2 1)
  176. 	// // 	when number of twos is odd  : 2 1 1       (1 1, 2)
  177. // 	
  178. 	// //so if we have ones and total is even then it is ok
  179. // 	
  180. // 	
  181. 	// //if we don't have ones then number of twos must be even
  182. 	// if(twos&1)cout<<"NO\n";
  183. 	// else cout<<"YES\n";
  184. // 	
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192. 	// if( (ones+2*twos)&1 )return void (cout<<"NO\n");
  193. // 	
  194. 	// int sm= (ones + 2*twos)/2;
  195. // 	
  196. 	// if( (sm%2==0) || ((sm&1) && ones) ) cout<<"YES\n";
  197. 	// else cout<<"NO\n";
  198. // 	
  199.  
  200. }
  201.  
  202. signed main(){
  203. 	ios::sync_with_stdio(0);cin.tie(0);
  204.  
  205. 	pre_compute();
  206.  
  207. 	int tc=1;
  208. 	if(multicases_)cin>>tc;
  209. 	int total_tcs=tc;
  210. 	while(tc--){
  211. 		solve(total_tcs-tc);
  212. 	}
  213. 	return 0;
  214. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5
2
1 1
2
1 2
4
1 2 1 2
3
2 2 2
3
2 1 2
stdout
copy 
YES
NO
YES
NO
NO
https://ideone.com/41LTYW
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!