OJ Board

Code: Select all

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

int main(){
  int n, m, s;
  bool a[45002];

  a[0] = 1;

  scanf( "%d", &n );
  
  for ( int i = 0; i < n; i++ ){
    memset( a, 0, 45002 * sizeof( bool ) );
    a[0] = 1;
    int sum = 0;
    scanf( "%d", &m );
    for ( int j = 0; j < m; j++ ){
      scanf( "%d", &s );
      sum += s;
      for ( int k = 45001; k >= s; k-- ){
        a[k] |= a[k-s];
      }
    }
    
    for ( int k = ( sum ) / 2 ; k >= 0; k-- ){
      if ( a[k] ){ printf("%d %d\n", k, ( sum ) - k );
      break;
      }
    }
  }
}

Code: Select all

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

typedef vector<int>::reverse_iterator VI;

int main ()
{
  int N, Num;

  cin >> N;
  for (int i=0; i<N; i++)
  {
    long equip1 = 0;
    long equip2 = 0;
    cin >> Num;
    vector<int> gent(Num);
    stack<int> SEquip1;
    stack<int> SEquip2;
    for (int j=0; j<Num; j++) cin >> gent[j];
    sort(gent.begin(),gent.end());

    for (VI p=gent.rbegin(); p!=gent.rend(); p++)
    {
      if (equip1>equip2)
      {
        equip2+=(*p);
        SEquip2.push(*p);
      }
      else
      {
        equip1+=(*p);
        SEquip1.push(*p);
      }
    }
    // Equilibrem
    while (abs((int)SEquip1.size() - (int)SEquip2.size())>1)
    {
      if (((int)SEquip1.size() - (int)SEquip2.size())>0)
      {
        SEquip2.push(SEquip1.top());
        equip2+=SEquip1.top();
        equip1-=SEquip1.top();
        SEquip1.pop();
      }
      else
      {
        SEquip1.push(SEquip2.top());
        equip1+=SEquip2.top();
        equip2-=SEquip2.top();
        SEquip2.pop();
      }
    }

    if (equip1>equip2) cout << equip2 << " " << equip1 << endl;
    else cout << equip1 << " " << equip2 << endl;
  }
}