結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー ont
提出日時 2025-06-25 16:03:01
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,725 bytes
コンパイル時間 7,631 ms
コンパイル使用メモリ 335,000 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2025-06-25 16:03:15
合計ジャッジ時間 11,547 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 MLE * 4 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define NP next_permutation
const int INF32 = 2e9;
const ll INF64 = 2e18;
const ll mod = 998244353;
// const ll mod = 1e9 + 7;
template<typename T> bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;}
 
void cincout() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
}
 
int main() {
    cincout();
 
    ll N, D, K;
    cin >> N >> D >> K;
    vector<ll> 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<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(D + 1, vector<ll>(501, -INF64))); //dp[i][j][k]:iまででj個選び、美しさがkになった時の満足度の最大値
    dp[0][0][0] = 0;
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j <= D; j++) {
            for (ll k = 0; k <= 500; k++) {
                if (dp[i][j][k] == -INF64) continue;
                //選ぶとき
                if (j < D) chmax(dp[i + 1][j + 1][min(k + C[i], 500LL)], dp[i][j][k] + A[i]);
                //選ばないとき
                chmax(dp[i + 1][j][k], dp[i][j][k]);
            }
        }
    }

    ll ans = -INF64;
    for (int k = K; k <= 500; k++) chmax(ans, dp[N][D][k]);
    if (ans != -INF64) cout << ans << endl;
    else cout << "No" << endl;
}
0