USACO 2012 January Contest, Bronze Division, Problem 1. Gifts

USACO Computiong Olympiad , January 2012 Contest , Problem 1. Gifts

Problema: http://www.usaco.org/index.php?page=viewproblem2&cpid=103
Para resolverlo utilize una estructura COST ( P = price y S = shipping cost ) , como solo puedo reducir el precio de un solo elemento, lo que se me ocurrio fue hacer una fuerza bruta, por cada uno de los regalos dividirlo entre dos y luego ordenarlo , utilizo el arreglo copy para mi modificacion y ordenacion asi no pierdo mi configuracion orignal sin reduccion que lo tengo en el arreglo gifts.
Para que ordeno?
Si mis datos estan ordenamos la mejor forma de dar regalos es siempre comprando los de menor precio ( P + S ), y asi queda el algoritmo ( la complejidad el algoritmo es de N ^ 2 * log N ( ordenacion ( N log N ) por N iteraciones ) ):

/*
   Autor: Rodrigo Burgos Dominguez
   Problema: Gift
*/
# include "stdio.h"
# include "string.h"

typedef struct { int P, S; } COST;

COST gifts[1002], copy[ 1002 ];

int max( int a, int b ){ return a > b ? a : b; }

int compare( COST *a, COST *b){
  int ca = a->P + a->S, cb = b->P + b->S;
  if( ca < cb) return -1;
  if( ca > cb) return +1;
  return 0;   
}

main(){
  int n, B, x, y, sol = 0, budget;
  freopen("gifts.in","r", stdin);
  freopen("gifts.out","w", stdout);
  scanf("%d %d", &n, &B);
  for( x = 0; x < n; x++) scanf("%d %d", &gifts[x].P, &gifts[x].S);
  for( x = -1; x < n; x++){
     for( y = 0; y < n; y++) copy[ y ] = gifts[ y ];
     if( x >= 0 ){
        copy[ x ].P /= 2;
      qsort( copy , n, sizeof( COST ), compare);
      budget = B;
      for(y = 0; y < n; y++){
        budget -=  ( copy[y].P + copy[y].S);
        if( budget < 0 ) break;
      }
      sol = max( sol, y );
     } 
  }
  printf("%d\n", sol);
  return 0; 
}