Cod sursa(job #2502481)

Utilizator DariusDCDarius Capolna DariusDC Data 30 noiembrie 2019 22:10:50
Problema Energii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("energii.in");
ofstream fout("energii.out");

int n, G;
int e[1005], g[1005];

int dp[2][5005]; //dp[i][j] = cost minim pentru a avea cel putin energia j, folosind primele i elemente
int k;

int s;

inline void MakeInf()
{
    for (int i = 0; i <= G; i++)
        dp[k][i] = 2e9;
}

inline void read()
{
    fin >> n >> G;
    for (int i = 1; i <= n; i++)
        fin >> e[i] >> g[i], s += e[i];
}

inline void solve()
{
    k = 1-k;
    MakeInf();
    for (int i = 1; i <= n; i++)
    {
        k = 1 - k;
        MakeInf();
        for (int j = 1; j <= G; j++)
        {
            if (j <= e[i])
                dp[k][j] = min(dp[1 - k][j], g[i]);
            else
                dp[k][j] = min(dp[1 - k][j], dp[1 - k][j - e[i]] + g[i]);
        }
    }
    fout << dp[k][G];
}

int main()
{
    read();
    if (s < G)
        fout << "-1";
    else
        solve();
    return 0;
}