Cod sursa(job #1266399)
| Utilizator | Data | 18 noiembrie 2014 18:12:06 | |
|---|---|---|---|
| Problema | Energii | Scor | 5 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.47 kb |
#include <fstream>
using namespace std;
int e[10000],c[10000],d[10000];
ifstream in("energii.in");
ofstream out("energii.out");
int main() {
int n,i,j,sol,g,g2,k,l=0;
in>>n>>g;
for (i=1;i<=n;i++){
in>>e[i]>>c[i];
g2+=c[i];}
for (i=1;i<=n;i++)
for (j=g2-c[i];j>=0;j--)
if (d[j+c[i]]<d[j]+e[i]) d[j+c[i]]=d[j]+e[i];
while (l<=g2){
l++;
if (d[l]>=g) {out<<l;l=g2;}
}
if (d[g2]<g) out<<"-1";
}
