Cod sursa(job #10192)

Utilizator DranaXumAlexandru Dumitru Paunoiu DranaXum Data 27 ianuarie 2007 23:14:00
Problema Energii Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream.h>

int a[1002],b[1002],c[1002];

int main()
{
   long int s,s1,s2,min=-1;
   int t,g,w,ok=1,i;
   ifstream fin("energii.in");
   ofstream fout("energii.out");
   fin>>g>>w;
   s=0;
   for(i=1;i<=g;i++)
   {   fin>>a[i]>>b[i]; s+=a[i];}
   fin.close();
   if(s<w) fout<<-1;
   else
   {
      
      /*while(ok)
      {  s1=s2=0;
         c[g]++;
         ok=0;
         for(i=g;i>=1;i--)
         {
            t=c[i];
            if(c[i]>1) 
            {  c[i]=t%2;
               c[i-1]+=t/2;}
            if(!c[i]) ok=1;
            else {s1+=a[i]; s2+=b[i];}
         }  
         if(s1>=w)
            if(min<0) min=s2; 
            else if(min>=s2) min=s2;
      }*/
      //min=0; 
      s1=s2=0;
      int max2=0,poz2,max=0,poz,tmp;
      s=w; tmp=g;
      while((w>0) && (g>0)){
         for(i=1;i<=g;i++)
            if(max<a[i]){ max=a[i]; poz=i;}
         t=a[g];   
         a[g]=a[poz];
         a[poz]=t;
         
         g--;
         w-=max;
         s1+=b[poz];
      }
      w=s; g=tmp;
      while((w>0) && (g>0)){
         for(i=1;i<=g;i++)
         {   if(min<0) {min=b[i]; poz=i;} else
            if(min>b[i]) {min=b[i]; poz=i;}
            }
         
         t=b[g];
         b[g]=b[poz];
         b[poz]=t;
         g--;
         w-=a[poz];
         s2+=t;
      }
      if(s1>s2) min=s2;
      else min=s1;
   }
   fout<<min;
   fout.close();
   return 0;
}