OJ Board

Code: Select all

#include <cstdio>
#include <memory>
#define abs(a) ((a)>=0?(a):-(a))
int main(){
    int q;
    scanf("%d",&q);
    while(q--){
               bool *a1=new bool[501];
               bool *a2=new bool[501];
               bool *now;
               bool *tmp;
               memset(a1,false,501);
               memset(a2,false,501);
               a1[0]=true;
               now=a1;
               tmp=a2;
               int m;
               scanf("%d",&m);
               while(m--){
                          int n;
                          scanf("%d",&n);
                          for(int i=0;i<=500;i++)
                                  if(now[i]){
                                  tmp[i]=false;
                                  if (i+n<=500)
                                     tmp[i+n]=true;
                                  tmp[abs(i-n)]=true;
                                  }
                          bool *e=tmp;
                          tmp=now;
                          memset(tmp,false,501);
                          now =e;
               }
               for(int i=0;i<=500;i++)
                       if (now[i]){
                          printf("%d\n",i);
                          break;
                       }
    }
    return 0;
}

Code: Select all

      W = sum/2;
		for(i = 0; i <= W; i++)A[0][i] = 0;		
		for(i = 1; i <= n; i++)
		{
			A[i][0] = 0;
			for(j = 1; j <= W; j++)
			{
				if(v[i] <= j)
				{
					if(v[i] + A[i-1][j-v[i]] > A[i-1][j])A[i][j] = v[i] + A[i-1][j-v[i]];
					else A[i][j] = A[i-1][j];
				}
				else A[i][j] = A[i-1][j];
			}
		}
		printf("%d\n",sum-2*A[n][W]);

Code: Select all

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int compare_function(const void *a, const void *b);

int main()
{
    //freopen("input2.txt","r",stdin);
    //freopen("output2.txt","w",stdout);
    
    int testCase;
    
    cin >> testCase;
    
    for (int i=0; i<testCase;i++){
        
        int n;
        
        cin >> n;
        
        if (n==0){
           cout << "0" << endl;
           continue;          
        }
        
        int values[n], totalValue = 0 , difference = 0;
        
        for(int j=0;j<n;j++){
                cin >> values[j];
                totalValue += values[j];
        }
        
        int averageVal = totalValue/2;
        
        qsort(values,n,sizeof(int),compare_function);       
        
        int valP1 , valP2 = 0;
        
        valP1 = values[0];
        
        if (valP1 >= averageVal){
                  for(int k=1;k<n;k++){
                          valP2 += values[k];
                  }
                  
                  if (valP1 > valP2)
                            difference = valP1 - valP2;
                  else
                            difference = valP2 - valP1;
                  
        }
        else{
             
             int bal1 , bal2;
             
             bal1 = averageVal - valP1;
             bal2 = averageVal - valP2;
             
             for (int j=1;j<n;j++){
                 if(bal1 < values[j]){
                         valP2 += values[j];
                         bal2 -= values[j];
                 }
                 else{
                         valP1 += values[j];
                         bal1 -= values[j];
                 }
                         
             }
             
             
        }

        
        if (valP1 > valP2)
                            difference = valP1 - valP2;
        else
                            difference = valP2 - valP1;
        
        
        cout << difference << endl;
    }
    

    system ("pause");
    return 0;
}

int compare_function(const void *a, const void *b){
    
    int *x = (int *) a;
    int *y = (int *) b;
    return *y - *x;
    
}

Code: Select all

sh: pause: not found

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXWEIGHT 25100 // The maximum sum of coins is 50000, so the maximum possible to get is 50000/2 = 25000
#define MAXITENS 110

int c[MAXITENS][MAXWEIGHT];

void dp_01_knapsack(int weights[], int values[], int n, int W){
    int w, i;
    //for (w = 0; w <= W; w++)
    //    c[0][w] = 0;
    memset(c[0], 0, sizeof(int) * (W+1));
    for (i = 1; i <= n; ++i){
        c[i][0] = 0;
        for (w = 1; w <= W; ++w){
            if ((weights[i] <= w) && (values[i] + c[i-1][w-weights[i]])){
                c[i][w] = values[i] + c[i-1][w-weights[i]];
            }else{
                c[i][w] = c[i-1][w];
            }
        }
    }
    #ifdef _DEBUG_
    for (i = n, w = W; i > 0; --i){
        if (c[i][w] != c[i-1][w]){
            printf("Take %d\n", weights[i]);
            w -= weights[i];
        }else{
            printf("Leave %d\n", weights[i]);
        }
    }
    #endif
}

int getdiff(int coins[], int ncoins, int sum){
    int i, w;
    int tot_take = 0, tot_leave = 0;
    
    dp_01_knapsack(coins, coins, ncoins, sum/2);
    
    for (i = ncoins, w = sum/2; i > 0; --i){
        if (c[i][w] != c[i-1][w]){
            tot_take += coins[i];
            w -= coins[i];
        }else{
            tot_leave += coins[i];
        }
    }
    return tot_leave > tot_take ? tot_leave - tot_take : tot_take - tot_leave;
}

int main(void){
    int ncases, ncoins, sum, i;
    int coins[MAXITENS];
    
    scanf(" %d", &ncases);
    while(ncases--){
        sum = 0;
        scanf(" %d", &ncoins);
        for (i = 1; i <= ncoins; i++){
            scanf(" %d", &coins[i]);
            sum += coins[i];
        }
        printf("%d\n", getdiff(coins, ncoins, sum));
    }
    return 0;
}