Cod sursa(job #699645)

Utilizator flaviu.stefanlupu flaviu flaviu.stefan Data 29 februarie 2012 20:38:29
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <fstream>
#include <iostream>
#include <string.h>
#define INF 0x3f3f3f3f
using namespace std;
int g,w,a[1005][5005],e[1005],c[1005],i,j;
int min(int a, int b)
{
if(a>b)
return b;
else
return a;
}
int main()
{
ifstream f("energii.in");
ofstream h("energii.out");
f>>g>>w;
for(i=1; i<=g; i++)
{
f>>e[i]>>c[i];
}
memset(a,INF,sizeof(a));
for(i=1; i<=g; i++)
for(j=1; j<=w; j++)
if(j<=e[i])
a[i][j]=min(a[i-1][j],c[i]);
else
a[i][j]=min(a[i-1][j],a[i-1][j-e[i]]+c[i]);
if(a[g][w]==INF)
h<<-1;
else
h<<a[g][w];
return 0;
}