結果
問題 | No.189 SUPER HAPPY DAY |
ユーザー | kotamanegi |
提出日時 | 2017-03-14 23:02:48 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 44 ms / 5,000 ms |
コード長 | 1,621 bytes |
コンパイル時間 | 663 ms |
コンパイル使用メモリ | 93,340 KB |
実行使用メモリ | 36,136 KB |
最終ジャッジ日時 | 2023-09-12 12:23:52 |
合計ジャッジ時間 | 2,409 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,532 KB |
testcase_01 | AC | 3 ms
5,984 KB |
testcase_02 | AC | 3 ms
5,680 KB |
testcase_03 | AC | 4 ms
5,912 KB |
testcase_04 | AC | 4 ms
5,924 KB |
testcase_05 | AC | 4 ms
5,964 KB |
testcase_06 | AC | 4 ms
5,928 KB |
testcase_07 | AC | 4 ms
5,872 KB |
testcase_08 | AC | 3 ms
5,908 KB |
testcase_09 | AC | 4 ms
6,096 KB |
testcase_10 | AC | 3 ms
5,916 KB |
testcase_11 | AC | 4 ms
5,972 KB |
testcase_12 | AC | 3 ms
5,880 KB |
testcase_13 | AC | 27 ms
21,568 KB |
testcase_14 | AC | 34 ms
23,668 KB |
testcase_15 | AC | 30 ms
21,604 KB |
testcase_16 | AC | 29 ms
21,104 KB |
testcase_17 | AC | 36 ms
25,596 KB |
testcase_18 | AC | 28 ms
21,416 KB |
testcase_19 | AC | 42 ms
29,588 KB |
testcase_20 | AC | 18 ms
15,464 KB |
testcase_21 | AC | 21 ms
15,744 KB |
testcase_22 | AC | 7 ms
8,388 KB |
testcase_23 | AC | 21 ms
20,184 KB |
testcase_24 | AC | 24 ms
21,400 KB |
testcase_25 | AC | 44 ms
36,136 KB |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include<map> #include <iomanip> #include <time.h> #include <random> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> using namespace std; #define LONG_INF 10000000000000000 #define MAX_MOD 1000000009 #define REP(i,n) for(long long i = 0;i < n;++i) long long plus_map[2][10000] = {}; long long dper[2][300][2][5000] = {}; int main() { string a, b; cin >> a >> b; for (int i = 0;i < 2;++i) { string m; if (i == 0) { m = a; } else m = b; dper[i][0][1][0] = 1; for (int q = 0;q < m.length();++q) { for (int j = 0;j < 4000;++j) { //どの数でも選べる for (int t = 0;t < 10;++t) { dper[i][q+1][0][t + j] += dper[i][q][0][j]; dper[i][q+1][0][t + j] %= MAX_MOD; } //どの数でも選べない for (int t = 0;t < m[q] - '0';++t) { dper[i][q+1][0][t + j] += dper[i][q][1][j]; dper[i][q+1][0][t + j] %= MAX_MOD; } dper[i][q+1][1][j + (m[q] - '0')] += dper[i][q][1][j]; dper[i][q+1][1][j + (m[q] - '0')] %= MAX_MOD; } } for (int q = 1;q < 5000;++q) { plus_map[i][q] = dper[i][m.length()][0][q] + dper[i][m.length()][1][q]; plus_map[i][q] %= MAX_MOD; } } long long ans = 0; for (int i = 1;i < 5000;++i) { ans += plus_map[0][i] * plus_map[1][i]; ans %= MAX_MOD; } cout << ans << endl; return 0; }