Cod sursa(job #1131203)

Utilizator andreiseiceanSeicean Andrei andreiseicean Data 28 februarie 2014 18:26:34
Problema Energii Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#define maxw 5006
using namespace std;

ifstream f("energii.in"); ofstream o("energii.out");
int a[1006][maxw],g,w;


void pd(int p,int x, int y,int&ct){
int i,d;
if (p==1) {
    for (i=1;i<=x;i++) a[p][i]=y;
    ct=x;
}
else {
    for (i=1;i<=x;i++) {if (a[p-1][i]) a[p][i]=min(a[p-1][i],y);
                        else a[p][i]=y; }
    //d=a[p-1][x];
    ct += x;
    if (ct>w) ct=w+1;
    for (i=x+1;i<=ct;i++) if(a[p-1][i]) a[p][i]=min(a[p-1][i],a[p-1][i-x]+y);
                                            else a[p][i]=a[p-1][i-x]+y; }

}


void citire(){
int i,x,y,r;
f>>g>>w;
r=0;
for (i=1;i<=g;i++){
    f>>x>>y;
    pd(i,x,y,r);
}

}

void afisare(){
if (a[g][w]) o<<a[g][w]; else o<<-1;
}


int main(){
citire();
afisare();
return 0;
}