提出詳細

ソースコード

#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:46:50
問題 J - 質より量 (large)
ユーザ名 konchan
状態 形式違反
正解率 N/A
提出出力結果

テストケース情報

# 状態 詳細情報
正解か誤答の場合のみ表示されます．