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. 	//now iterative (only 1d) dp
  78.  
  79. 	if(total&1)return void(cout<<"NO\n");
  80.  
  81.  
  82. 	int target=total/2;
  83.  
  84. 	vector<bool>dp(target+1,false);
  85.  
  86. 	//now the state is s (summation) 
  87. 		// it represents wheter the s is reachable from the n elements we have or no 
  88.  
  89.  
  90. 	dp[0]=true;
  91. 	for(int x:v){
  92.  
  93. 		for(int s = target ;s>=x;s--){
  94. 			dp[s]=dp[s]||dp[s-x];
  95. 			//     ^ the leave case 
  96. 								//(if it was already reached before using this candy)
  97. 			//the take case through dp[s-x]
  98. 				//which means if this candy of weight x was taken
  99. 					//then can i make the remaining s-x before taking it?
  100.  
  101. 		//important question : why the order of the loop is reversed
  102.  
  103.  
  104.  
  105. 		}
  106.  
  107. 	}
  108.  
  109. 	cout<<(dp[target]?"YES\n":"NO\n");
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122. 	// //iterative dp now:
  123. // 	
  124. 	// //if total is not divisible by 2 then immediately reurn the output NO\n 
  125. 	// if (total % 2) {
  126.         // cout << "NO\n";
  127.         // return;
  128.     // }
  129. //     
  130. //     
  131. 	// int target=total/2;//focus error fix:total/2 not n/2
  132. 	// vector<vector<bool>>dp(n+1,vector<bool>(target+1,false));
  133. // 	
  134. 	// //states : dp[i][s] => i means how many candies are we allowed to use
  135. 	// //					=> s means what sum are we trying to make
  136. // 	
  137. // 	
  138. 	// //base case: we can build sum of 0 using 0 candies
  139. 	// dp[0][0]=true;
  140. 	// //all s values for i=1 is false
  141. 		// //because when you don't choose anything all what you can make is 1
  142. // 	
  143. // 	
  144. 	// for(int i = 1 ;i <= n ;i++){	//you have now i elements to build your target
  145. // 		
  146. 		// for(int s = 0; s<=target;s++){	//know if s is reachable from the i indices
  147. 												// //may be some of them 
  148. // 			
  149. 			// //leave
  150. 			// //if i can make s without the current candy 
  151. 				// //then it can be done with the current candy also
  152. 			// dp[i][s]=dp[i-1][s];
  153. // 			
  154. // 			
  155. 			// //take
  156. 			// //if i take the current one, can the previous ones build the remaining ?
  157. 			// if(s>=v[i-1]){
  158. 				// dp[i][s]=dp[i][s]||dp[i-1][s-v[i-1]];
  159. 			// }
  160. // 			
  161. 		// }
  162. // 		
  163. 	// }
  164. // 	
  165. // 	
  166. 	// //now the question is can i build the target from the n elements
  167. 						// // and the target is total/2
  168. 	// // so if we can build the half of the sum from the n elements
  169. 				// //then the reamining half is the rest untaken cells
  170. 	// cout<<(dp[n][target]?"YES\n":"NO\n");
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185. 	// int ones=count(v.begin(),v.end(),1),twos=count(v.begin(),v.end(),2);
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194. // 	
  195. 	// int sm=ones+twos*2;
  196. // 	
  197. 	// //summation of all values must be even
  198. 	// if(sm&1) return void (cout<<"NO\n");
  199. // 	
  200. 	// //if total is even and we have someones so these ones summation must be even
  201. 			// //becuase twos are actually even so also ones summation is even
  202. 										// //to make the total sum even
  203. // 	
  204. 	// //if we have ones (and as proved summation of ones is even)
  205. 	// if(ones)return void (cout<<"YES\n"); 
  206. // 	
  207. // 	
  208. 	// //examples
  209. 	// // 	when number of twos is even : 2 2 1 1     (2 1 , 2 1)
  210. 	// // 	when number of twos is odd  : 2 1 1       (1 1, 2)
  211. // 	
  212. 	// //so if we have ones and total is even then it is ok
  213. // 	
  214. // 	
  215. 	// //if we don't have ones then number of twos must be even
  216. 	// if(twos&1)cout<<"NO\n";
  217. 	// else cout<<"YES\n";
  218. // 	
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226. 	// if( (ones+2*twos)&1 )return void (cout<<"NO\n");
  227. // 	
  228. 	// int sm= (ones + 2*twos)/2;
  229. // 	
  230. 	// if( (sm%2==0) || ((sm&1) && ones) ) cout<<"YES\n";
  231. 	// else cout<<"NO\n";
  232. // 	
  233.  
  234. }
  235.  
  236. signed main(){
  237. 	ios::sync_with_stdio(0);cin.tie(0);
  238.  
  239. 	pre_compute();
  240.  
  241. 	int tc=1;
  242. 	if(multicases_)cin>>tc;
  243. 	int total_tcs=tc;
  244. 	while(tc--){
  245. 		solve(total_tcs-tc);
  246. 	}
  247. 	return 0;
  248. }
Success #stdin #stdout 0.01s 5324KB
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/EuJiL8
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!