結果

問題 No.189 SUPER HAPPY DAY
ユーザー ttkkggwwttkkggww
提出日時 2022-09-10 18:31:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 1,737 bytes
コンパイル時間 4,117 ms
コンパイル使用メモリ 263,344 KB
実行使用メモリ 16,352 KB
最終ジャッジ日時 2023-08-17 22:44:00
合計ジャッジ時間 5,742 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
16,088 KB
testcase_01 AC 6 ms
16,064 KB
testcase_02 AC 6 ms
16,112 KB
testcase_03 AC 6 ms
16,188 KB
testcase_04 AC 6 ms
16,352 KB
testcase_05 AC 6 ms
16,032 KB
testcase_06 AC 7 ms
16,180 KB
testcase_07 AC 7 ms
16,112 KB
testcase_08 AC 6 ms
16,044 KB
testcase_09 AC 7 ms
16,240 KB
testcase_10 AC 7 ms
16,040 KB
testcase_11 AC 7 ms
16,036 KB
testcase_12 AC 7 ms
16,044 KB
testcase_13 AC 25 ms
16,048 KB
testcase_14 AC 29 ms
16,184 KB
testcase_15 AC 27 ms
16,048 KB
testcase_16 AC 27 ms
16,048 KB
testcase_17 AC 27 ms
16,056 KB
testcase_18 AC 26 ms
16,352 KB
testcase_19 AC 35 ms
16,312 KB
testcase_20 AC 14 ms
16,040 KB
testcase_21 AC 18 ms
16,096 KB
testcase_22 AC 9 ms
16,020 KB
testcase_23 AC 21 ms
16,044 KB
testcase_24 AC 16 ms
16,036 KB
testcase_25 AC 31 ms
16,056 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
次のファイルから読み込み:  /usr/include/atcoder/modint:1,
         次から読み込み:  /usr/include/atcoder/convolution.hpp:11,
         次から読み込み:  /usr/include/atcoder/convolution:1,
         次から読み込み:  /usr/include/atcoder/all:1,
         次から読み込み:  main.cpp:3:
メンバ関数 ‘atcoder::dynamic_modint<id>::mint& atcoder::dynamic_modint<id>::operator+=(const mint&) [with int id = -1]’ 内,
    inlined from ‘void solve()’ at main.cpp:57:67:
/usr/include/atcoder/modint.hpp:192:9: 警告: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
  192 |         _v += rhs._v;
      |         ^~
main.cpp: 関数 ‘void solve()’ 内:
main.cpp:55:32: 備考: within this loop
   55 |                 for(int j = 1;j<10;j++){
      |                               ~^~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using ll = long long;
string M,D;
using mint = modint;
mint dp1[202][2][4000];
mint dp2[202][2][4000];

void solve(){
	for(auto &i:M)i-='0';
	for(auto &i:D)i-='0';
	for(int i = 1;i<M[0];i++){
		dp1[1][1][i+2000-1] = 1;
	}
	dp1[1][0][M[0]+2000-1] = 1;
	for(int i =1;i<M.size();i++){
		for(int j = 1;j<10;j++){
			dp1[i+1][1][j+2000-1] += 1;
		}
		for(int j = 0;j<10;j++){
			for(int k =0;k<4000;k++){
				if(k+j<4000){
					dp1[i+1][1][k+j] += dp1[i][1][k];
				}
				
			}
		}
		for(int j = 0;j<M[i];j++){
			for(int k = 0;k<4000;k++){
				if(k+j<4000){
					dp1[i+1][1][k+j] += dp1[i][0][k];
				}
			}
		}
		for(int k = 0;k<4000;k++){
			if(k+M[i]<4000){
				dp1[i+1][0][k+M[i]] += dp1[i][0][k];
			}
		}
	}
	for(int i = 0;i<4000;i++){
		for(int j = 1;j<D[0];j++){
			if(i-j+1>=0)
				dp2[1][1][i-j+1] += dp1[M.size()][0][i] + dp1[M.size()][1][i];
		}
	}
	for(int i = 0;i<4000;i++){
		if(i-D[0]+1>=0){
			dp2[1][0][i-D[0]+1] += dp1[M.size()][0][i] + dp1[M.size()][1][i];
		}
	}
	for(int i = 1;i<D.size();i++){
		for(int j = 1;j<10;j++){
			for(int k =0;k< 4000;k++){
				dp2[i+1][1][k-j+1] += dp1[M.size()][0][k] + dp1[M.size()][1][k];
			}
		}
		for(int k = 0;k<4000;k++){
			for(int j = 0;j<10;j++){
				if(k-j>=0){
					dp2[i+1][1][k-j] += dp2[i][1][k];
				}
			}
			for(int j = 0;j<D[i];j++){
				if(k-j>=0){
					dp2[i+1][1][k-j] += dp2[i][0][k];
				}
			}
			if(k-D[i]>=0){
				dp2[i+1][0][k-D[i]] += dp2[i][0][k];
			}
		}
	}
	mint ans = dp2[D.size()][0][2000] + dp2[D.size()][1][2000];
	cout<<ans.val()<<endl;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	mint::set_mod(1000000009);
	cin >> M >> D;
	solve();
}
0