Cod sursa(job #2725652)

Utilizator KlinashkaDiacicov Calin Marian Klinashka Data 19 martie 2021 14:02:16
Problema Energii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>
using namespace std;

const int INF = (int)1e9;

int main() {
	freopen("energii.in", "r", stdin);
	freopen("energii.out", "w", stdout);
	int g, w;
	cin >> g >> w;
	int dp[g+1][w+1] = {}; // costul minim pt a genera cel putin w energie
	int eg[g+1], cg[g+1];
	for(int i=1;i<=g;i++)
		cin >> eg[i] >> cg[i];
	for(int i=0;i<=w;i++)
		dp[0][i] = INF;

	for(int i=1;i<=g;i++) {
		for(int j=0;j<=w;j++) {
			if(j<=eg[i])
				dp[i][j] = min(dp[i-1][j], cg[i]);
			else
				dp[i][j] = min(dp[i-1][j], dp[i-1][j-eg[i]]+cg[i]);
		}
	}

	if(dp[g][w] >= INF)
		cout << "-1\n";
	else
		cout << dp[g][w] << '\n';

	return 0;
}