Cod sursa(job #1674516)

Utilizator Vasile_RotaruVasea Rotaru Vasile_Rotaru Data 4 aprilie 2016 18:22:02
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.46 kb
#include<bits/stdc++.h>

using namespace std;

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

int G,W,EG,CG,op[5002],i,j;

int main()
{
	fin>>G>>W;
	for(i=1;i<=W;++i)op[i]=999999;
	for(i=1;i<=G;++i)
	{
		fin>>EG>>CG;
		if(EG>=W)
		{
			if(CG<op[W])op[W]=CG;
			continue;
		}
			
		for(j=W;j>0;--j)
			if(j<EG)op[j]=min(op[j],CG);
			else op[j]=min(op[j-EG]+CG,op[j]);
	}
	if(op[W]==999999)fout<<-1;
	else fout<<op[W];
 	return 0;
}