Cod sursa(job #2044862)
Utilizator | Data | 21 octombrie 2017 15:25:24 | |
---|---|---|---|
Problema | Energii | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.61 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("energii.in");
ofstream g("energii.out");
int n,G,i,ma,j,gr[10001], p[10001], b[10001];
int main()
{
f>>n>>G;
for(i=1;i<=n;++i)
f>>gr[i]>>p[i];
b[gr[1]]=p[1];
for(i=2;i<=n;++i)
{
for(j=G-gr[i];j>=1;--j)
if(b[j]>0)
if(b[gr[i]+j] <b[j]+p[i])
b[gr[i]+j]=b[j]+p[i];
if(b[gr[i]]<p[i])
b[gr[i]]=p[i];
}
ma=0;
for(i=G;i>=1;--i)
if(b[i]>ma)
ma=b[i];
if(ma<G)
g<<-1;
else
g<<ma;
return 0;
}