結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
![]() |
提出日時 | 2023-08-19 20:30:54 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,201 bytes |
コンパイル時間 | 2,875 ms |
コンパイル使用メモリ | 141,220 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 08:04:24 |
合計ジャッジ時間 | 4,119 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#include<iostream>#include<vector>#include<atcoder/all>using namespace std;int main( void ){int N, K;cin >> N >> K;vector<int> sp( N ), fp( N );for( int i = 0; i < N; i++ ){cin >> fp[i];}for( int i = 0; i < N; i++ ){cin >> sp[i];}int ans1 = 0, ans2 = 1;vector<int> dp1( K + 1, 0 );vector<atcoder::modint998244353> dp2( K + 1, 0 );dp2[0] = 1;for( int i = 1; i <= K; i++ ){for( int j = 0; j < N; j++ ){if( i - fp[j] < 0 ) continue;if( dp1[i] < dp1[i - fp[j]] + sp[j] ){dp1[i] = dp1[i - fp[j]] + sp[j];dp2[i] = dp2[i - fp[j]];}else if( dp1[i] == dp1[i - fp[j]] + sp[j] ){dp2[i] += dp2[i - fp[j]];}}if( ans1 < dp1[i] || ( ans1 == dp1[i] && ans2 < dp2[i].val() ) ){ans1 = dp1[i];ans2 = dp2[i].val();}else if( ans1 == dp1[i] && ans2 == dp2[i].val() ){ans2 += dp2[i].val();}}cout << ans1 << endl << ans2 << endl;return 0;}