Cod sursa(job #3173624)

Utilizator adrian_zahariaZaharia Adrian adrian_zaharia Data 23 noiembrie 2023 13:43:58
Problema Energii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;
const int nax=1005;
const int mod=1e9+7;
const int inf=INT_MAX;

int n;
int G,W;
int e,c;
struct gen{
    int e,c;
};

int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);

    long long suma=0;
    scanf("%d %d",&G,&W);
    vector <gen> g;
    for(int i=1;i<=G;i++){
        scanf("%d %d",&e,&c);
        g.push_back({.e=e,.c=c});
        suma+=e;
    }
    if(suma<W){
        printf("-1");
        return 0;
    }
    vector<int> dp(W+1,1e9);
    dp[0]=0;

//    for(int i=1;i<=G;i++){
//        printf("%d %d\n",g[i].e,g[i].c);
//    }

    for(int i=0;i<G;i++){
        for(int q=W-1;q>=0;q--){
            int j=min(q+g[i].e,W);
            dp[j]=min(dp[j],dp[q]+g[i].c);
        }
    }
    printf("%d ",dp[W]);

    return 0;
}