Cod sursa(job #2000793)
Utilizator | Data | 14 iulie 2017 19:26:47 | |
---|---|---|---|
Problema | Energii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.78 kb |
#include<bits/stdc++.h>
using namespace std;
int d[10005];
int main()
{
freopen("energii.in","r",stdin);
freopen("energii.out","w",stdout);
int n,G,g,p,i,last,j,max1=0;
d[0]=0;
scanf("%d%d",&n,&G);
for(i=1;i<=G;i++)
d[i]=-1;
last=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&g,&p);
for(j=last;j>=0;j--)
{
if(j+g<=G)
{
if(d[j]!=-1)
{
if(d[j]+p>d[j+g])
{
d[j+g]=d[j]+p;
if(j+g>last) last=j+g;
}
}
}
}
}
for(i=G;i>=0;i--)
if(d[i]>max1) max1=d[i];
printf("%d",max1);
return 0;
}