結果

問題 No.3014 岩井満足性問題
ユーザー ZOI-dayo
提出日時 2025-02-22 02:12:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 124 ms / 3,000 ms
コード長 893 bytes
コンパイル時間 3,325 ms
コンパイル使用メモリ 279,872 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-22 02:12:47
合計ジャッジ時間 5,542 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

signed main() {
int n, D, K; 
  cin>> n>>D>>K;
  vector<int> a(n), c(n);
  for(int i=0; i<n; i++) cin>>a[i];
  for(int i=0; i<n; i++) cin>>c[i];
  vector dp (n+1, vector<int>(K+1, -6'000'000'000'00ll));
  dp[0][0] = 0;
  for(int i=0; i<n; i++) {
    for(int j=n; j>=0; j--) {
      for(int k=0; k<=K; k++) {
        if(dp[j][k] == -6'000'000'000'00LL) continue;
        chmax(dp[j+1][min(K, k+c[i])], dp[j][k] + a[i]);
      }
    }
  }
  /*
  int ans = -1;
  for(int i=0; i<n+1; i++) {
    for(int j=0; j<n+1; j++) {
      for(int k=0; k<=D; k++) {
        cout << i << " " << j << " " << k << " " << dp[i][j][k] << endl;
      }
    }
  }
  */
  int ans = dp[D][K];
  if(ans == -6'000'000'000'00LL) cout << "No" << endl;
  else cout << ans << endl;

}
0