Cod sursa(job #3173568)

Utilizator adrian_zahariaZaharia Adrian adrian_zaharia Data 23 noiembrie 2023 10:35:57
Problema Energii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <bits/stdc++.h>

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

int n;
int G,W;
int e,c;
struct gen{
    int e,c;
};
int dp[nax];
int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);

    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});
    }
    dp[0]=1;

//    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;q>=g[i].e;q--){
            if(dp[q-g[i].e]){
                if(dp[q]){
                    dp[q]=min(dp[q],dp[q-g[i].e]+g[i].e);
                }else{
                    dp[q]=dp[q-g[i].c]+g[i].c;
                }
            }
        }
    }
//    for(int i=0;i<=W;i++){
//        printf("%d ",dp[i]);
//    }
    printf("%d",dp[W]);

    return 0;
}