結果
問題 | No.137 貯金箱の焦り |
ユーザー |
![]() |
提出日時 | 2022-12-30 14:42:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 588 bytes |
コンパイル時間 | 580 ms |
コンパイル使用メモリ | 68,544 KB |
最終ジャッジ日時 | 2025-02-09 22:05:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 1 WA * 22 |
ソースコード
#include <iostream> using namespace std; typedef long long ll; ll mod = 1234567891,dp[200010],a[110]; int main(){ ll i,j,n,m; cin >> n >> m; for(i=0;i<n;i++) cin >> a[i]; dp[0] = 1; int sum = 0; for(i=0;i<n;i++) sum += a[i]; while(m){ for(i=0;i<n;i++){ for(j=2*sum;j>=a[i];j--){ (dp[j] += dp[j - a[i]]) %= mod; } } for(j=0;j<=2*sum;j++){ ll nx = 2*j + m&1; if(nx<=2*sum) dp[j] = dp[nx]; else dp[j] = 0; } m /= 2; } cout << dp[0] << "\n"; }