Jisseikatsu-Algorithm-1-5-2.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, L;
int V[1009], W[1009];
int dp[1009][10009][2];

int main() {
	// Step #1. 入力
	cin >> N >> L;
	for (int i = 1; i <= N; i++) cin >> V[i] >> W[i];

	// Step #2. 動的計画法・出力
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= L; j++) {
			for (int k = 0; k < 2; k++) {
				if (i >= 11 && i <= 20) {
					// パンの場合
					if (j < W[i]) dp[i][j][k] = dp[i - 1][j][k];
					else if (k == 0) dp[i][j][k] = dp[i - 1][j][k];
					else dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - W[i]][0] + V[i]);
				}
				else {
					// パン以外の場合
					if (j < W[i]) dp[i][j][k] = dp[i - 1][j][k];
					else dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - W[i]][k] + V[i]);
				}
			}
		}
	}
	cout << dp[N][L][1] << endl;
	return 0;
}