結果
問題 |
No.189 SUPER HAPPY DAY
|
ユーザー |
|
提出日時 | 2023-09-18 01:47:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,458 bytes |
コンパイル時間 | 1,613 ms |
コンパイル使用メモリ | 175,320 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-07-04 18:43:35 |
合計ジャッジ時間 | 3,165 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 5 WA * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007; int main() { string M, D; cin >> M >> D; int M_sz = M.size(); int D_sz = D.size(); vector<vector<vector<ll>>>dp1(250, vector<vector<ll>>(2, vector<ll>(2000, 0))); vector<vector<vector<ll>>>dp2(250, vector<vector<ll>>(2, vector<ll>(2000, 0))); dp1[0][0][0] = 1; dp2[0][0][0] = 1; for (int i = 0; i < M_sz; i++) { int mi = M[i] - '0'; for (int j = 0; j < 2; j++) { for (int k = 0; k <= 1800; k++) { for (int d = 0; d <= (j ? 9 : mi); d++) { dp1[i+1][j || (d < mi)][k+d] += dp1[i][j][k]%MOD; } } } } for (int i = 0; i < D_sz; i++) { int di = D[i] - '0'; for (int j = 0; j < 2; j++) { for (int k = 0; k <= 1800; k++) { for (int d = 0; d <= (j ? 9 : di); d++) { dp2[i+1][j || (d < di)][k+d] += dp2[i][j][k]%MOD; } } } } ll ans = 0; ll tmp1, tmp2; for (int i = 1; i <= 1800; i++) { tmp1 = dp1[M_sz][0][i]%MOD + dp1[M_sz][1][i]%MOD; tmp2 = dp2[D_sz][0][i]%MOD + dp2[D_sz][1][i]%MOD; ans += (tmp1%MOD) * (tmp2%MOD); ans %= MOD; } cout << ans << endl; return 0; }