結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー u_kun
提出日時 2025-01-25 13:48:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 540 ms / 3,000 ms
コード長 3,148 bytes
コンパイル時間 1,181 ms
コンパイル使用メモリ 104,992 KB
実行使用メモリ 7,196 KB
最終ジャッジ日時 2025-01-25 23:00:07
合計ジャッジ時間 3,987 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge10
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:59:23: warning: overflow in conversion from ‘double’ to ‘long long int’ changes value from ‘-1.0e+20’ to ‘-9223372036854775808’ [-Woverflow]
   59 | const long long INF = -1e20;
      |                       ^~~~~

ソースコード

diff # 

/*
N, D, K = map(int, input().split())
A = list(map(int, input().split()))
C = list(map(int, input().split()))

INF = -10**20

dp = [[INF for col in range(N + 1)] for row in range(K + 1)]
dp[0][0] = 0

for sel in range(D + 1):
    
    ne_dp = [[INF for col in range(N + 1)] for row in range(K + 1)]
    
    for col in range(N):
        for row in range(K + 1):
            
            if dp[row][col] != INF:
                
                # 選ぶ
                if sel != D:
                    ne_row = row + C[col]
                    ne_row = min(ne_row, K)
                    
                    if ne_dp[ne_row][col + 1] == INF:
                        ne_dp[ne_row][col + 1] = dp[row][col] + A[col]
                    else:
                        ne_dp[ne_row][col + 1] = max(ne_dp[ne_row][col + 1], dp[row][col] + A[col])
                    
                
                # 選ばない
                if dp[row][col + 1] == INF:
                    dp[row][col + 1] = dp[row][col]
                else:
                    dp[row][col + 1] = max(dp[row][col + 1], dp[row][col])
    

    if sel != D:
        dp = ne_dp

ans = INF

for col in range(N + 1):
    if dp[K][col] != INF:
        ans = max(ans, dp[K][col])

if ans == INF:
    print("No")
else:
    print(ans)
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = -1e20;

int main() {
    int N, D, K;
    cin >> N >> D >> K;
    
    vector<long long> A(N);
    vector<long long> C(N);
    
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    vector<vector<long long>> dp(K + 1, vector<long long>(N + 1, INF));
    dp[0][0] = 0;

    for (int sel = 0; sel <= D; sel++) {
        vector<vector<long long>> ne_dp(K + 1, vector<long long>(N + 1, INF));

        for (int col = 0; col < N; col++) {
            for (int row = 0; row <= K; row++) {
                if (dp[row][col] != INF) {
                    // 選ぶ
                    if (sel != D) {
                        int ne_row = row + C[col];
                        ne_row = min(ne_row, K);
                        
                        if (ne_dp[ne_row][col + 1] == INF) {
                            ne_dp[ne_row][col + 1] = dp[row][col] + A[col];
                        } else {
                            ne_dp[ne_row][col + 1] = max(ne_dp[ne_row][col + 1], dp[row][col] + A[col]);
                        }
                    }

                    // 選ばない
                    if (dp[row][col + 1] == INF) {
                        dp[row][col + 1] = dp[row][col];
                    } else {
                        dp[row][col + 1] = max(dp[row][col + 1], dp[row][col]);
                    }
                }
            }
        }

        if (sel != D) {
            dp = move(ne_dp);
        }
    }

    long long ans = INF;
    for (int col = 0; col <= N; col++) {
        if (dp[K][col] != INF) {
            ans = max(ans, dp[K][col]);
        }
    }

    if (ans == INF) {
        cout << "No" << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}
0