結果
問題 |
No.3014 岩井満足性問題
|
ユーザー |
![]() |
提出日時 | 2025-02-22 02:06:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 665 ms / 3,000 ms |
コード長 | 1,499 bytes |
コンパイル時間 | 1,993 ms |
コンパイル使用メモリ | 200,536 KB |
実行使用メモリ | 7,072 KB |
最終ジャッジ日時 | 2025-02-22 02:06:09 |
合計ジャッジ時間 | 5,254 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> PP; // #define MOD 1000000007 #define MOD 998244353 #define INF 2305843009213693951 #define PI 3.141592653589 #define setdouble setprecision #define REP(i,n) for(ll i=0;i<(n);++i) #define OREP(i,n) for(ll i=1;i<=(n);++i) #define RREP(i,n) for(ll i=(n)-1;i>=0;--i) #define ORREP(i,n) for(ll i=(n);i>=1;--i) #define rep(i,a,b) for(ll i=(a);i<=(b);++i) #define ALL(v) (v).begin(), (v).end() #define chmin(k,m) k = min(k,m) #define chmax(k,m) k = max(k,m) #define GOODBYE do { cout << "-1" << endl; return 0; } while (false) #define MM <<" "<< #define Endl endl int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); ll N,D,K; cin >> N >> D >> K; vector<ll> A(N),C(N); REP(i,N){ cin >> A[i]; } REP(i,N){ cin >> C[i]; } // dp[i][j] := 美しさが min(i,K) で、 // D 個採用したときの満足度の最大値 vector<vector<ll>> dp(K+1,vector<ll>(D+1,-INF)); dp[0][0] = 0; REP(k,N){ vector<vector<ll>> tmp(K+1,vector<ll>(D+1,-INF)); REP(i,K+1){ REP(j,D+1){ if(j+1<=D){ chmax(tmp[min(K,i+C[k])][j+1],dp[i][j]+A[k]); } chmax(tmp[i][j],dp[i][j]); } } swap(dp,tmp); } ll Ans = dp[K][D]; if(Ans<=-INF/10){ cout << "No" << endl; }else{ cout << Ans << endl; } return 0; }