結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー bal4u
提出日時 2019-08-29 16:51:52
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 11 ms / 5,000 ms
コード長 1,492 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 31,232 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-17 16:56:18
合計ジャッジ時間 1,226 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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