結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー YFYF
提出日時 2025-01-25 14:09:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,229 bytes
コンパイル時間 4,596 ms
コンパイル使用メモリ 260,564 KB
実行使用メモリ 814,848 KB
最終ジャッジ日時 2025-01-25 23:09:39
合計ジャッジ時間 30,975 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other MLE * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
long long N,D,K;
vector<long long> A,C;
vector<vector<vector<long long>>> memory;
const long long INF = 1LL << 60;
long long dp(long long n,long long k,long long d){
    long long& ret = memory[n][k][d];
    if(ret != -1)return ret;

    ret = -INF;
    if(n == 0){
        if(k == 0 && d == 0)ret = 0;
        return ret;
    }

    if(d == 0){
        if(k == 0)ret = 0;
        return ret;
    }

    chmax(ret,dp(n-1,k,d));
    chmax(ret,dp(n-1,max(0LL,k-C[n-1]),d-1) + A[n-1]);
    return ret;
}
int main() {
    cin >> N >> D >> K;

    rep(i,N){
        long long a;
        cin >> a;
        A.push_back(a);
    }
    rep(i,N){
        long long a;
        cin >> a;
        C.push_back(a);
    }

    memory.resize(501,vector<vector<long long>>(501,vector<long long>(501,-1)));

    if(dp(N,K,D) > -1e12)cout << dp(N,K,D) << endl;
    else cout << "No" << endl;


}
0