Cod sursa(job #518141)

Utilizator ioanabIoana Bica ioanab Data 30 decembrie 2010 16:26:40
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
using namespace std;

ifstream in("energii.in");
ofstream out("energii.out");

int ct[100000],g[20000],c[20000],ok,i,j,n,w,minim,maxim,maxt;

int main()
{
	in>>n;
	in>>w;
	
	
	for(i=0;i<=10000;i++)
		ct[i]=-1;
	
	for(i=1;i<=n;i++)
	{
		in>>g[i]; 
		in>>c[i];
	}
	
	for(i=1;i<=n;i++)
		 {
			for(j=maxim;j>=0;j--)
				if(j==0 && (ct[j+g[i]]==-1||ct[j+g[i]]>ct[j]+c[i]))
				{
					 ct[j+g[i]]=ct[j]+c[i]+1;
					 if(j+g[i]>maxim) maxim=j+g[i];
				}
				else
					if(j!=0&&ct[j]!=-1&&(ct[j+g[i]]>ct[j]+c[i]||ct[j+g[i]]==-1))
					{
						ct[j+g[i]]=ct[j]+c[i];
						if(j+g[i]>maxim) 
							maxim=j+g[i];
					}

			  if(maxim>=w) 
			  {
				  if(maxt<maxim) maxt=maxim;
						 maxim=w;
			  }
		  }
	
	 minim=32000;
	 if(maxt==0) 
	 {
		 out<<"-1"; 
		 return 0;
	 }
	 if(maxt==w) 
	 {
		 out<<ct[w]; 
		 return 0;
	 }
	 for(i=w;i<=maxt;i++)
		  if(minim>ct[i]&&ct[i]!=-1) minim=ct[i];
	 out<<minim;
	
	return 0;
}