Cod sursa(job #2751308)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 14 mai 2021 18:55:01
Problema Energii Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>

#define NMAX 1000
#define WMAX 5000
#define INFINIT 10000000 + 1 //1e7 + 1

using namespace std;

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

int ener[NMAX + 1];
int cost[NMAX + 1];
int rsp[WMAX + 1];

int main()
{
    int N, W;
    fin >> N >> W;

    int sumaEnergie = 0;
    for(int i = 1; i <= N; i++){
        fin >> ener[i] >> cost[i];
        sumaEnergie += ener[i];
    }

    if(sumaEnergie < W){
        fout << -1;
        return 0;
    }

    for(int j = 1; j <= W; j++){
        rsp[j] = INFINIT;
    }
    rsp[0] = 0;
    for(int i = 1; i <= N; i++){
        for(int j = W; j >= ener[i]; j--){
            rsp[j] = min( rsp[j], rsp[ j - ener[i] ] + cost[i] );
        }
        for(int j = ener[i] - 1; j >= 1; j--){ //pentru ca lucrez cu un vector in locul unei matrici!
            rsp[j] = INFINIT;
        }
    }

    fout << rsp[W];

    return 0;
}