結果
問題 | No.41 貯金箱の溜息(EASY) |
ユーザー | srjywrdnprkt |
提出日時 | 2022-12-20 01:14:19 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 23 ms / 5,000 ms |
コード長 | 722 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 108,628 KB |
実行使用メモリ | 4,428 KB |
最終ジャッジ日時 | 2023-08-11 10:10:18 |
合計ジャッジ時間 | 1,754 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 22 ms
4,428 KB |
testcase_01 | AC | 23 ms
4,412 KB |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> #include <complex> using namespace std; const long long modc = 1e9+9; int main(){ long long T, M, q; cin >> T; vector<long long> dp(90001), S(90001); dp[0] = 1; for (int j=1; j<=9; j++){ for (int i=0; i<=90000; i++){ if (i-j >= 0) dp[i] = (dp[i] + dp[i-j]) % modc; } } S[0] = 1; for (int i=1; i<=90000; i++){ S[i] = (S[i-1] + dp[i]) % modc; } for (int i=0; i<T; i++){ cin >> M; q = M / 111111; cout << S[q] << endl; } return 0; }