Cod sursa(job #2449923)

Utilizator petrisorvmyVamanu Petru Gabriel petrisorvmy Data 21 august 2019 10:39:35
Problema Energii Scor 45
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;

ifstream f("energii.in");
ofstream g("energii.out");
int n, v[1005], pd[10001 * 1001], w[1005], G,maxim;
int main()
{
    f >> n >> G;
    for(int i = 1; i <= n; ++i)
    {
        f >> v[i] >> w[i];
        maxim += v[i];
    }
    if(maxim < G)
    {
        g << -1;
        f.close();
        g.close();
        return 0;
    }
    for(int i = 1; i <= maxim; ++i)
        pd[i] = INF;
    for(int i = 1; i <= n; ++i)
        for(int j = maxim - v[i]; j >= 0; --j)
            if(pd[j] != INF)
                pd[j + v[i]] = min(pd[j + v[i]], pd[j] + w[i]);
    int minim = INF;
    for(int i = G; i <= maxim; ++i)
    {
        if(pd[i] != INF)
        {
            minim = min(pd[i], minim);
        }
    }
    g << minim;
    f.close();
    g.close();
    return 0;
}