fork download
copy 
  1. //Ishan Bansal
  2. //handle:ishan.nitj at codeforces ,ishan_nitj at codechef
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define inf 1000000000000000000
  7. #define MOD 1000000007
  8. #define rep(i,n) for(i=0;i<n;i++)
  9. #define print_array(a,n) for(i=0;i<n;i++) printf("%lld ",a[i]);
  10. #define mset(x,v) memset(x, v, sizeof(x))
  11. #define dbg1(x) cout<<#x<<" "<<x<<endl;
  12. #define dbg2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
  13. #define dbg3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
  14. #define dbg4(x,y,z,k) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<" "<<#k<<" "<<k<<endl;
  15. #define pb push_back
  16. #define fe first
  17. #define se second
  18. #define mag 12
  19.    ll subset[250000+1][500+1];
  20.  ll balancePartition(ll set[], ll n)
  21. {
  22.  /*The value of subset[i][j] will be true if there is a subset 
  23.      of set[0..j-1] with sum equal to i */
  24.         ll i,j;
  25.         ll sum =0;
  26.  
  27.         for(i =0; i<=n; i++){
  28.                 sum += set[i];
  29.         }
  30.  
  31.  
  32.         // If sum is 0, then answer is true
  33.         for (i = 0; i <= n; i++)
  34.                 subset[0][i] = true;
  35.  
  36.         // If sum is not 0 and set is empty, then answer is false
  37.         for (i = 1; i <= sum; i++)
  38.                 subset[i][0] = false;
  39.  
  40.  
  41.         // Fill the subset table in botton up manner
  42.         for (i = 1; i <= sum; i++)
  43.         {
  44.          for ( j = 1; j <= n ; j++)
  45.          {
  46.            subset[i][j] = subset[i][j-1];
  47.            if (i >= set[j-1]){
  48.               subset[i][j] = subset[i][j] ||subset[i-set[j-1]][j-1];
  49.            }
  50.          }
  51.         }
  52.  
  53.         ll min =inf;
  54.  
  55.         for(i=1; i<=sum; i++){
  56.            for(j=1; j<=n; j++){
  57.            /* If there is s subset with sum i, then check if the 
  58.               difference between overall sum and twice this sum is least or not.
  59.               If yes update the min */
  60.  
  61.               if(subset[i][j] == true){
  62.                    if(abs(sum - 2*i) < min){
  63.                        min  = abs(sum - 2 *i);
  64.                    }
  65.               }
  66.            }
  67.         }
  68.  
  69. return min;
  70. }
  71.  
  72. int main(){
  73. std::ios::sync_with_stdio(false);
  74. cin.tie(0);
  75. //freopen("OP.txt","r",stdin);
  76. //freopen("IP.txt","w",stdout);
  77. ll t;cin>>t;
  78. while(t--){
  79. mset(subset,0);
  80. ll n;cin>>n;
  81. ll i;
  82. vector<ll>v;
  83. rep(i,n){
  84. ll x;string s;
  85. cin>>x>>s;
  86. v.pb(x);
  87. }
  88. ll x;cin>>x;v.pb(x);
  89. vector<ll>v1,v2;
  90. for(i=0;i<v.size();i++){
  91. if(i%2==0)
  92. v1.pb(v[i]);
  93. else
  94. v2.pb(v[i]);
  95. }
  96. ll arr1[v1.size()],arr2[v2.size()];
  97. for(i=0;i<v1.size();i++)
  98. arr1[i]=v1[i];
  99. for(i=0;i<v2.size();i++)
  100. arr2[i]=v2[i];
  101. ll ans=balancePartition(arr1,v1.size()-1)+balancePartition(arr2,v2.size()-1);
  102. cout<<ans<<endl;
  103. }
  104.  
  105. } 
  106.  
  107.  
Runtime error #stdin #stdout 1.07s 982016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MdgKiX
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!