USACO 3.1.2 – Score Inflation

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
	freopen("inflate.in", "r", stdin), freopen("inflate.out", "w", stdout);
	int M, N, w[10001], c[10001], best[10001];
	scanf("%d %d\n%d %d\n", &M, &N, w, c);

	for (int i = 0; i < N; i++, scanf("%d %d\n", w+i, c+i))
		for (int j = c[i]; j <= M; j++)
			best[j] = max(best[j], best[j - c[i]] + w[i]);

	printf("%d\n", best[M]);
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: