Cod sursa(job #464615)
#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 *= 2;
for (i=1; i<=S; ++i)
c[i] = 2000000;
for (i=1; i<=n; ++i)
for (j=S; j>=0; --j)
if (energie[i] <= j && cost[i] + c[j-energie[i]] < c[j])
c[j] = cost[i] + c[j-energie[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;
}