AtCoderのABC015_D問題でWAになる

Question

前提・実現したいこと

ABC015のD問題が一部のケースでACになりません。方針としてはdp[i][j][k]をi - 1枚目までのスクショを考慮し、幅がj以下で使用枚数がk以下の時の最大の価値としたのですが、どこに誤りがあるのかわかりません。何卒ご教授のほどよろしくお願いします。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = INT_MAX;


template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int MAX_N = 60, MAX_W = 10100;
const int MAX_K = 60;
int dp[MAX_N][MAX_W][MAX_K];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int W, N, K; cin >> W >> N >> K;
    int a[N], b[N]; for(int i = 0; i < N; ++i) cin >> a[i] >> b[i];
    for(int i = 0; i < N; ++i){
        for(int sum_w = 0; sum_w <= W; ++sum_w){
            for(int j = 0 ; j <= K; j++){
                    if(sum_w >= a[i] ){
                        chmax(dp[i + 1][sum_w][j + 1], dp[i][sum_w - a[i]][j] + b[i]);
                    }
                    chmax(dp[i + 1][sum_w][j + 1], dp[i][sum_w][j]);
                }
            }
    }
    int res = 0;
    for(int i = 0; i <= N; i++){
        for(int j = 0; j <= W; ++j){
            for(int k = 0; k <= K; ++k){
                chmax(res, dp[i][j][k]);
            }
        }
    }
    cout << res << endl;


}

Answer 1

3
3 2
1 10
10 10
1 10
=> 10

正しい答えは20です

Comments

[rdld036]

具体的な反例をあげてくださりありがとうございます。私の質問文が曖昧でしたが、私のコードのどの部分に誤りまたは不足があるのか教えていただけますか。

[yudedako67]

スクリーンショットを使わない場合が正しく考慮されていません

[rdld036]

確かにdpの添字はj + 1ではなく、単にjでよかったですね。ご指摘していただきありがとうございます。