結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
|
提出日時 | 2023-08-28 19:51:15 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,757 ms / 2,000 ms |
コード長 | 1,129 bytes |
コンパイル時間 | 1,681 ms |
コンパイル使用メモリ | 171,196 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-12 08:06:03 |
合計ジャッジ時間 | 8,524 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define pll pair<ll,ll>#define pii pair<int,int>#define fs first#define sc secondconst int mxn = 1010;const ll mod = 998244353;const ll inf = 1e18;pll dp[2][mxn];inline ll mad(ll a,ll b){a += b;return a>=mod?a-mod:a;}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll n,k;cin>>n>>k;pll arr[n];for(auto &i:arr)cin>>i.fs;for(auto &i:arr)cin>>i.sc;bool roll = false;pll big = {0,1};for(auto &i:dp)for(auto &j:i)j = {-inf,0};dp[roll][0] = {0,1};for(int i = 0;i<k;i++){roll ^= 1;for(int j = 0;j<=k;j++)dp[roll][j] = {-inf,0};for(auto &p:arr){for(int j = p.fs;j<=k;j++){auto &tmp = dp[roll^1][j-p.fs];if(tmp.fs+p.sc>dp[roll][j].fs)dp[roll][j] = {tmp.fs+p.sc,tmp.sc};else if(tmp.fs+p.sc == dp[roll][j].fs)dp[roll][j].sc = mad(dp[roll][j].sc,tmp.sc);}}for(int j = 0;j<=k;j++){if(big.fs<dp[roll][j].fs)big = dp[roll][j];else if(big.fs == dp[roll][j].fs)big.sc = mad(big.sc,dp[roll][j].sc);}}cout<<big.fs<<'\n'<<big.sc;}