結果

問題 No.42 貯金箱の溜息
コンテスト
ユーザー izuru_matsuura
提出日時 2016-10-25 20:53:16
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 1,578 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,065 ms
コンパイル使用メモリ 113,520 KB
実行使用メモリ 16,128 KB
最終ジャッジ日時 2024-06-12 04:42:55
合計ジャッジ時間 13,479 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void log(A...)(A arg) {
    stdout.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

void main() {
    const long mod = cast(long)(1e9 + 9);
    long[] C = [1, 5, 10, 50, 100, 500];
    int T = readln.chomp.to!int;
    foreach (_; 0 .. T) {
        long M = readln.chomp.to!long;
        long[] W;
        long[] sum;
        void init() {
            long m = 1;
            for (; m <= M; m <<= 1) {
                foreach (c; C) {
                    if (0 < m * c && m * c <= M) {
                        W ~= m * c;
                    }
                }
            }
            W.sort!"a > b";
            sum = new long[W.size + 1];
            for (int i = W.size - 1; i >= 0; i--) {
                auto w = W[i];
                sum[i] = sum[i + 1] + w;
                if (sum[i] < 0) sum[i] = long.max;
            }
        }
        init();

        long[Tuple!(int, long)] cache;
        long dfs(int n, long x) {
            if (x == 0) return 1;
            if (n == W.size || x < 0) return 0;
            if (sum[n] < x) return 0;
            auto key = tuple(n, x);
            if (key in cache) return cache[key];
            //log([n], [x], (dfs(n + 1, x) + dfs(n + 1, x - W[n])) % mod);
            return cache[key] = (dfs(n + 1, x) + dfs(n + 1, x - W[n])) % mod;
        }
        
        writeln(dfs(0, M));
    }
}
0