結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー biotea
提出日時 2025-01-25 14:58:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 999 bytes
コンパイル時間 1,521 ms
コンパイル使用メモリ 161,340 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2025-01-25 23:37:18
合計ジャッジ時間 3,111 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// #include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll inf = (1LL << 61);
ll dx[4] = {0, 1, 0, -1};
ll dy[4] = {-1, 0, 1, 0};
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define REP(i, init, n) for (ll i = (ll)init; i < (ll)(n); ++i)
// ll op(ll a, ll b) { return max(a, b); }
// ll e() { return -inf; }
ll a[510], c[510];
ll dp[2][510][510];
int main() {
  ll n, d, K;
  cin >> n >> d >> K;
  rep(i, n) cin >> a[i];
  rep(i, n) cin >> c[i];
  ll cur = 0;
  rep(i, 2) rep(j, 510) rep(k, 510) dp[i][j][k] = -inf;
  dp[1][0][0] = 0;
  rep(i, n) {
    REP(j, 1, d + 1) {
      rep(k, K + 1) {
        dp[cur][j][k] = dp[1 - cur][j][k];
        if (k >= c[i] && dp[1 - cur][j - 1][k - c[i]] != -inf)
          dp[cur][j][k] = max(dp[cur][j][k], dp[1 - cur][j - 1][k - c[i]] + a[i]);
      }
    }
    cur = 1 - cur;
  }
  auto ans = dp[1 - cur][d][K];
  if (ans == -inf)
    cout << "No" << endl;
  else
    cout << dp[1 - cur][d][K] << endl;
}
0