poj 3977

なぜかWAになる
こんどまた解き直す。
保存用

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;
int n,n2;
long long int d[50];
typedef pair<long long int,int> P;
P ps[1 << (40 / 2)];

int main(){
  
  while(1){
  
  scanf("%d",&n);
  if(n == 0)break;
  for(int i = 0;i < n;i++){
    scanf("%lld",&d[i]);
  }
  n2 = n / 2;
  
  for(int i = 0;i < 1 << n2;i++){
    int co=0;
    long long int sw=0;
    for(int j = 0;j < n2;j++){
      if(i >> j & 1){
	sw += d[j];
	co++;
      }
    }
    ps[i] = P(sw,co);
  }
  
  sort(ps,ps + (1 << n2));
  /*
  for(int i = 0;i < 1 << n2;i++){
    cout << ps[i].first << endl;
  }
cout << "~~~~~~~~~~~~~~" << endl;
*/
  long long int ans = 1000000000000000000;
  int ans2 = 100;
  for(int i = 0;i < 1 << (n - n2);i++){
    long long int sw = 0;
    int co = 0;
    for(int j = 0;j < n - n2;j++){
      if(i >> j & 1){
	sw += d[n2 + j];
	co++;
      }
    }
  //  cout << sw << ":" << co <<endl;
    int lb = 0,ub = (1 << n2) -1;
  //  cout << "ub:" << ub << ",lb:" << lb << endl;
    while(ub - lb > 1){
      int mid = (ub + lb) / 2;
      if(ps[mid].first >= -sw) ub = mid;
      else lb = mid;
    }
    if(co != 0 || ps[lb].second != 0){
      if(llabs(sw+ps[lb].first) < llabs(ans)){
      ans = llabs(sw+ps[lb].first);
      ans2 = co + ps[lb].second;
      }
      if(llabs(sw+ps[lb].first) == llabs(ans))ans2 = min(ans2,co+ps[lb].second);
    }
    if(co != 0 || ps[ub].second != 0){
      if(llabs(sw+ps[ub].first) < llabs(ans)){
      ans = llabs(sw+ps[ub].first);
      ans2 = co + ps[ub].second;
      }
      if(llabs(sw+ps[ub].first) == llabs(ans))ans2 = min(ans2,co+ps[ub].second);
    }
  }
  printf("%lld %d\n",llabs(ans),ans2);
  }
  
  return 0;
}