#include <iostream> #include <algorithm> #include <stdio.h> using namespace std; int T, i, j, k; int N, B; int main(){ cin >> T; int ans[T][2]; for(i = 0; i < T; i++){ans[i][0] = -1; ans[i][1] = -1;} // Tのループ for(i = 0; i < T; i++){ cin >> N; int P[N], V[N]; cin >> B; for(j = 0; j < N; j++){ scanf("%d %d", &P[j], &V[j]); } // 初期化 int dp[N + 1][B + 1]; for(j = 0; j < N + 1; j++){ for(k = 0; k < B + 1; k++){ dp[j][k] = -1; } } dp[0][0] = 0; // 計算 for(j = 0; j < N; j++){ for(k = 0; k < B + 1; k++){ if(dp[j][k] >= 0){ dp[j + 1][k] = max(dp[j][k], dp[j + 1][k]); if(k + P[j] <= B){ dp[j + 1][k + P[j]] = max(dp[j + 1][k + P[j]], dp[j][k] + V[j]); } } } } // 勝ちの最大を確かめる for(j = 0; j <= B; j++){ if(ans[i][1] <= dp[N][j]){ ans[i][0] = j; ans[i][1] = dp[N][j]; } } } for(i = 0; i < T; i++){ cout << "Case #" << i + 1 << ':' << endl; cout << ans[i][0] << ' ' << ans[i][1] << endl; } return 0; }
提出時間 | 2020-04-29 16:48:19 |
問題 | J - 質より量 (large) |
ユーザ名 | konchan |
状態 | 正解 |
正解率 | 50/50 |
# | 状態 | 詳細情報 |
---|---|---|
テストケース 1 | 正解 | 詳細を見る |
テストケース 2 | 正解 | 詳細を見る |
テストケース 3 | 正解 | 詳細を見る |
テストケース 4 | 正解 | 詳細を見る |
テストケース 5 | 正解 | 詳細を見る |
テストケース 6 | 正解 | 詳細を見る |
テストケース 7 | 正解 | 詳細を見る |
テストケース 8 | 正解 | 詳細を見る |
テストケース 9 | 正解 | 詳細を見る |
テストケース 10 | 正解 | 詳細を見る |
テストケース 11 | 正解 | 詳細を見る |
テストケース 12 | 正解 | 詳細を見る |
テストケース 13 | 正解 | 詳細を見る |
テストケース 14 | 正解 | 詳細を見る |
テストケース 15 | 正解 | 詳細を見る |
テストケース 16 | 正解 | 詳細を見る |
テストケース 17 | 正解 | 詳細を見る |
テストケース 18 | 正解 | 詳細を見る |
テストケース 19 | 正解 | 詳細を見る |
テストケース 20 | 正解 | 詳細を見る |
テストケース 21 | 正解 | 詳細を見る |
テストケース 22 | 正解 | 詳細を見る |
テストケース 23 | 正解 | 詳細を見る |
テストケース 24 | 正解 | 詳細を見る |
テストケース 25 | 正解 | 詳細を見る |
テストケース 26 | 正解 | 詳細を見る |
テストケース 27 | 正解 | 詳細を見る |
テストケース 28 | 正解 | 詳細を見る |
テストケース 29 | 正解 | 詳細を見る |
テストケース 30 | 正解 | 詳細を見る |
テストケース 31 | 正解 | 詳細を見る |
テストケース 32 | 正解 | 詳細を見る |
テストケース 33 | 正解 | 詳細を見る |
テストケース 34 | 正解 | 詳細を見る |
テストケース 35 | 正解 | 詳細を見る |
テストケース 36 | 正解 | 詳細を見る |
テストケース 37 | 正解 | 詳細を見る |
テストケース 38 | 正解 | 詳細を見る |
テストケース 39 | 正解 | 詳細を見る |
テストケース 40 | 正解 | 詳細を見る |
テストケース 41 | 正解 | 詳細を見る |
テストケース 42 | 正解 | 詳細を見る |
テストケース 43 | 正解 | 詳細を見る |
テストケース 44 | 正解 | 詳細を見る |
テストケース 45 | 正解 | 詳細を見る |
テストケース 46 | 正解 | 詳細を見る |
テストケース 47 | 正解 | 詳細を見る |
テストケース 48 | 正解 | 詳細を見る |
テストケース 49 | 正解 | 詳細を見る |
テストケース 50 | 正解 | 詳細を見る |