Cod sursa(job #2834986)
Utilizator | Data | 17 ianuarie 2022 22:44:58 | |
---|---|---|---|
Problema | Energii | Scor | 50 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.54 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("energii.in");
ofstream fout("energii.out");
int n,g,dp[5010],e[1010],w[1010],best=INT_MAX,i,cw;
int main()
{
fin>>n>>g;
for(i=1;i<=n;i++)
fin>>e[i]>>w[i];
for(i=0;i<=g;i++)
dp[i]=10010;
for(i=1;i<=n;i++)
for(cw=g;cw>=0;cw--)
if(cw>=w[i])
dp[cw]=min(dp[cw],dp[cw-e[i]]+w[i]);
else dp[cw]=min(dp[cw],w[i]);
if(dp[g]==10010)
fout<<"-1\n";
else fout<<dp[g]<<'\n';
return 0;
}