Cod sursa(job #2448090)

Utilizator ShayTeodor Matei Shay Data 15 august 2019 17:27:59
Problema Energii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

#define WMAX 5001
#define INF 0x3f3f3f3f
#define BUFFER_SIZE 1 << 12

int dp[WMAX];
char buffer[BUFFER_SIZE];
int pos = BUFFER_SIZE;

inline char next() {
	if (pos == BUFFER_SIZE) {
		fread(buffer, 1, BUFFER_SIZE, stdin);
		pos = 0;
	}
	
	return buffer[pos++];
}

inline int read() {
	int n = 0;
	char c = next();

	while (!('0' <= c && c <= '9')) {
		c = next();
	}

	while ('0' <= c && c <= '9') {
		n = (n << 3) + (n << 1) + (c - '0');
		c = next();
	}

	return n;
}

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

	int n, g, w, p;
	n = read(), g = read();
	int power[n + 1], costs[n + 1];
	memset(dp, INF, sizeof(dp));

	for (int i = 1 ; i <= n ; ++i) {
		power[i] = read(), costs[i] = read();
	}

	for (int i = 1 ; i <= n ; ++i) {
		for (int j = g ; j >= power[i] ; --j) {
			dp[j] = std::min(dp[j], dp[j - power[i]] + costs[i]);
		}

		for (int j = 1 ; j < power[i] ; ++j) {
			dp[j] = std::min(dp[j], costs[i]);
		}
	}

	dp[g - 1] == INF ? printf("-1") : printf("%d\n", dp[g - 1]);
	return 0;
}