Cod sursa(job #2276563)

Utilizator GarboteialexGarbotei Alex Garboteialex Data 4 noiembrie 2018 21:01:20
Problema Energii Scor 60
Compilator cpp-64 Status done
Runda alexei1 Marime 0.83 kb
#include <fstream>

using namespace std;

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

long long w,g;
long long dp[1002][10002];

struct centrala
{
    long long energie; long long cost;
} gn[1002];

int main()
{
    fin >> g >> w;
    for(int i = 1; i <= g; i++)
        fin >> gn[i].energie >> gn[i].cost;
    
    for(int i = 0; i <= g; i++)
        for(int j = 0; j <= w; j++)
            dp[i][j] = 9e8;
    
    for(int i = 1; i <= g; i++)
        for(int j = 0; j <= w; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(gn[i].energie >= j) dp[i][j] = min(dp[i][j], gn[i].cost);
            else dp[i][j] = min(dp[i][j], (dp[i - 1][j - gn[i].energie] + gn[i].cost));
        }
    
    if(dp[g][w] == 9e8) fout << "-1";
    else fout << dp[g][w];
    
    fin.close();
    fout.close();
    
    return 0;
}