Cod sursa(job #598883)

Utilizator deneoAdrian Craciun deneo Data 27 iunie 2011 14:26:11
Problema Energii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
#include <cstring>
using namespace std;

#define INF 0x3f3f3f3f

int n, w, cost[50010], gen[1010][3];

int main()
{
    int i, j, min = INF;

    ifstream f("energii.in");
    ofstream g("energii.out");
    f >> n >> w;

    memset(cost, -1, sizeof(cost));
    cost[0] = 0;

    for(i = 1; i <= n; ++i)
    {
        f >> gen[i][1] >> gen[i][2];
        for(j = 20000; j >= gen[i][1]; --j)
            if(cost[j - gen[i][1]] != -1 && ((cost[j - gen[i][1]] + gen[i][2] < cost[j]) || cost[j] == -1))
            {
                cost[j] = cost[j - gen[i][1]] + gen[i][2];
            }
    }

    for(i = w; i <= 20000; ++i)
        if(cost[i] < min && cost[i] != -1)
            min = cost[i];

    if(min == INF)
        g << -1 << '\n';
    else
        g << min << '\n';
    g.close();
    return 0;
}