結果

問題 No.189 SUPER HAPPY DAY
ユーザー bal4ubal4u
提出日時 2019-08-29 16:51:52
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 1,492 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 30,148 KB
実行使用メモリ 4,764 KB
最終ジャッジ日時 2023-08-11 04:05:20
合計ジャッジ時間 1,906 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,676 KB
testcase_01 AC 2 ms
4,664 KB
testcase_02 AC 3 ms
4,688 KB
testcase_03 AC 3 ms
4,632 KB
testcase_04 AC 2 ms
4,680 KB
testcase_05 AC 2 ms
4,752 KB
testcase_06 AC 3 ms
4,728 KB
testcase_07 AC 3 ms
4,720 KB
testcase_08 AC 3 ms
4,668 KB
testcase_09 AC 3 ms
4,728 KB
testcase_10 AC 3 ms
4,724 KB
testcase_11 AC 2 ms
4,724 KB
testcase_12 AC 3 ms
4,664 KB
testcase_13 AC 6 ms
4,648 KB
testcase_14 AC 8 ms
4,612 KB
testcase_15 AC 7 ms
4,732 KB
testcase_16 AC 8 ms
4,704 KB
testcase_17 AC 9 ms
4,740 KB
testcase_18 AC 6 ms
4,764 KB
testcase_19 AC 9 ms
4,732 KB
testcase_20 AC 4 ms
4,676 KB
testcase_21 AC 4 ms
4,736 KB
testcase_22 AC 3 ms
4,640 KB
testcase_23 AC 6 ms
4,732 KB
testcase_24 AC 8 ms
4,736 KB
testcase_25 AC 11 ms
4,732 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder: 189 SUPER HAPPY DAY
// 2019.8.29 bal4u

#include <stdio.h>
#include <string.h>

typedef long long ll;

#define gc() getchar()
int ins(char *s) { // 文字列の入力　スペース以下の文字で入力終了
	char *p = s--;
	do *++s = gc();
	while (*s > ' ');
	*s = 0;
	return s - p;
}

#define MOD 1000000009
int mcnt[1820], dcnt[1820];
int mma, dma;
char M[205]; int WM;
char D[205]; int WD;
int dp[205][1820][2];

inline static void chmod(int *a, ll b) { (*a) = (b + *a) % MOD; }

int calc(int *f, int w, char *s) {
	int i, j, k, a, ma;
	
	dp[0][0][1] = 1, ma = 0;
    for (i = 0; i < w; i++) {
        for (j = ma; j >= 0; j--) {
            for (k = 0; k < 2; k++) {
                if (k) {
					int d = s[i] & 0xf;
                    for (a = d-1; a >= 0; a--)
                        dp[i+1][j+a][0] = (dp[i+1][j+a][0] + dp[i][j][1]) % MOD;
                    dp[i+1][j+d][1] = (dp[i+1][j+d][1] + dp[i][j][1]) % MOD;
				} else {
                    for (a = 9; a >= 0; a--)
                        dp[i+1][j+a][0] = (dp[i+1][j+a][0] + dp[i][j][0]) % MOD;
                }
            }
        }
		ma += 9;
    }
	for (i = 1; i <= ma; i++) f[i] = (dp[w][i][0] + dp[w][i][1]) % MOD;
	return ma;
}

int main()
{
	int i, ans;
	
	WM = ins(M), WD = ins(D);
	mma = calc(mcnt, WM, M);
	
	memset(dp, 0, sizeof(dp));
	dma = calc(dcnt, WD, D);
	
	ans = 0;
	i = mma; if (i > dma) i = dma;
	while (i) chmod(&ans, (ll)mcnt[i]*dcnt[i]), i--;
	printf("%d\n", ans);
	return 0;
}
0