Cod sursa(job #639250)
Utilizator | Vacagrasa virginica Nustiunimic | Data | 22 noiembrie 2011 21:11:08 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 25 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
long long gr[100006],gr2[100006];
long long s,n,i,x,T,y,j,m,mx,mx2;
int main()
{
f>>n>>T;
for(i=1; i<=n; i++)
{
f>>x>>y;
for(j=1; j<=mx; j++)
{
if (gr[j]>0)
{
gr2[j+x]=max(gr[j+x],gr[j]+y);
mx2=max(mx2,j+x);
}
}
mx=max(mx,mx2);
gr2[x]=max(gr[x],y);
mx=max(mx,x);
for(j=1; j<=mx; j++)
gr[j]=gr2[j];
}
for(i=1;i<=T;i++)
m=max(gr[i],m);
g<<m;
f.close();
g.close();
return 0;
}