Cod sursa(job #2186)

Utilizator RazvanSSavu Razvan RazvanS Data 16 decembrie 2006 11:26:31
Problema Energii Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>

#define Nmax 5005
#define MAX 999999999

using namespace std;

ofstream fout("energii.out");
/*

void show(int V[], int W, int min, int max)
      {int i;
       for(i=0; i<=W+10; i++)
           fout<<V[i]<<" ";
       fout<<" *** "<<min<<" *** "<<max<<'\n';
       }     
          
*/      
      

int main(void)
    {int V[Nmax]={0}, n, C[Nmax], W, E[Nmax];
     ifstream fin("energii.in");
     fin>>n>>W;
     int i;
     for(i=1;i<=n; i++)
        fin>>E[i]>>C[i];
     fin.close();
     V[0]=1;
     int min=MAX, max=0, k, m;
     int j;
     for(i=1;i<=n;++i)
         {for(j=W-1;j>=0;--j)
              if(V[j]) {k=E[i]+j;
                        if(!j) m=0;
                           else m=V[j];
                        if(k>=W) { if(m+C[i]<min) min=m+C[i]; }
                           else  if(!V[k] && m+C[i] < V[k]) V[k]=m+C[i];
                                    
                                    
                        }
          // if(E[i]+max>=W) max=W-1;
          //    else  max+=E[i];
          // show(C,W,min,max);    
         }                
     //show(C,W,min);
     if(min==MAX) { fout<<"-1\n"; fout.close(); return 0;}
     
     fout<<min<<'\n';
     
     fout.close();
     
     return 0;
}