Cod sursa(job #464549)
#include <stdio.h>
using namespace std;
int c[100001], energie[10001], cost[10001];
int n, i, j, k;
int Min = 2000000;
long int suma, S;
int main ()
{
FILE *f = fopen ("energii.in","r");
FILE *g = fopen ("energii.out","w");
fscanf (f,"%d", &n);
fscanf (f,"%ld", &S);
for (i=1; i<=n; ++i)
{
fscanf (f,"%d %d", &energie[i], &cost[i]);
suma += energie[i];
}
if (S > suma)
{
fprintf (g,"-1");
return 0;
}
S *= 3;
for (i=1; i<=S; ++i)
c[i] = 2000000;
for (i=1; i<=n; ++i)
for (j=S; j>=0; --j)
if (cost[i] <= j && energie[i] + c[j-cost[i]] < c[j])
c[j] = energie[i] + c[j-cost[i]];
/*for (i=1; i<=S; ++i)
printf ("%d ", c[i]);*/
for (i=S; i>=S/2; --i)
if (c[i] < Min)
Min = c[i];
fprintf (g,"%d", Min);
fclose(g);
fclose(f);
return 0;
}