結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0