Cod sursa(job #1667956)
| Utilizator | Data | 29 martie 2016 13:32:47 | |
|---|---|---|---|
| Problema | Energii | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.7 kb |
#include <fstream>
#include <algorithm
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
int a[5005];
int main()
{
int G,W,EG,CG,i,j,s=0;
f>>G>>W;
for(i=1; i<=W; i++) a[i]=50000000;
for(i=1; i<=G; i++)
{
f>>EG>>CG;
s+=EG;
if(s<=W)
for(j=s;j>=EG;j--)
a[j]=min(a[j],a[j-EG]+CG);
else{
if(EG>=W)
a[W]=min(a[W],CG);
else
{for(j=W-EG;j<W;j++)
a[W]=min(a[W],a[j]+CG);
for(j=W-1;j>=EG;j--)
a[j]=min(a[j],a[j-EG]+CG);}}}
if(s<W)
g<<-1;
else
g<<a[W];
return 0;
}
