Cod sursa(job #785800)
Utilizator | Data | 9 septembrie 2012 21:18:46 | |
---|---|---|---|
Problema | Energii | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.51 kb |
#include <fstream>
using namespace std;
ifstream in("energii.in");
ofstream out("energii.out");
int maxi, n, i, j, m, e[1010], c[1010], a[15020];
int main(){
in>>n>>m;
for (i=1;i<=n;i++)
in>>e[i]>>c[i];
for (i=1;i<=15010;i++) a[i]=9999999;
a[0]=0;
for (i=1;i<=n;i++)
for (j=m;j>=0;j--)
if (a[j]!=-1&&a[j]+c[i]<a[j+e[i]]) a[j+e[i]]=a[j]+c[i];
maxi=9999999;
for (i=m;i<=15010;i++)
if (maxi>a[i]) maxi=a[i];
if (maxi!=9999999)out<<maxi;
else out<<-1;
return 0;
}