提出 #855588


ソースコード 拡げる

Copy
auto solve(long target, in int[] cards)
{
    import std.algorithm, std.range;
    immutable
        n = cards.length,
        m = cards.sum;
    auto dp = new long[][](n+1, m+1);
    dp[0][0] = 1;
    foreach (card; cards)
        foreach_reverse (usedCards; 0..n)
            foreach (currentSum; 0..m+1-card)
                dp[usedCards+1][currentSum+card] += dp[usedCards][currentSum];
    return 1.iota(n+1).map!(i => (i*target <= m) ? dp[i][cast(size_t)(i*target)] : 0).sum;
}

unittest
{
    import std.range, std.array;
    assert (8.solve([7, 9, 8, 9]) == 5);
    assert (8.solve([6, 6, 9]) == 0);
    assert (5.solve([3, 6, 2, 8, 7, 6, 5, 9]) == 19);
    assert (3.solve(3.repeat.take(33).array) == 8589934591);
}

void main()
{
    import std.stdio, std.string, std.array, std.conv;
    immutable
        target = readln.chomp.split[1].to!long,
        cards = readln.chomp.split.to!(int[]);
    target.solve(cards).writeln;
}

提出情報

提出日時
問題 C - 高橋君とカード
ユーザ majiang
言語 D (DMD64 v2.070.1)
得点 300
コード長 971 Byte
結果 AC
実行時間 63 ms
メモリ 1276 KB

ジャッジ結果

セット名 Sample Subtask1 All
得点 / 配点 0 / 0 200 / 200 100 / 100
結果
AC × 4
AC × 12
AC × 24
セット名 テストケース
Sample example_01.txt, example_02.txt, example_03.txt, example_04.txt
Subtask1 example_01.txt, example_02.txt, example_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt
All example_01.txt, example_02.txt, example_03.txt, example_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt
ケース名 結果 実行時間 メモリ
example_01.txt AC 3 ms 256 KB
example_02.txt AC 3 ms 256 KB
example_03.txt AC 3 ms 256 KB
example_04.txt AC 5 ms 256 KB
subtask1_01.txt AC 5 ms 380 KB
subtask1_02.txt AC 5 ms 380 KB
subtask1_03.txt AC 5 ms 380 KB
subtask1_04.txt AC 4 ms 256 KB
subtask1_05.txt AC 7 ms 380 KB
subtask1_06.txt AC 5 ms 256 KB
subtask1_07.txt AC 4 ms 256 KB
subtask1_08.txt AC 5 ms 380 KB
subtask1_09.txt AC 4 ms 380 KB
subtask2_01.txt AC 30 ms 892 KB
subtask2_02.txt AC 32 ms 892 KB
subtask2_03.txt AC 28 ms 892 KB
subtask2_04.txt AC 63 ms 1276 KB
subtask2_05.txt AC 54 ms 1276 KB
subtask2_06.txt AC 5 ms 256 KB
subtask2_07.txt AC 30 ms 892 KB
subtask2_08.txt AC 10 ms 508 KB
subtask2_09.txt AC 12 ms 508 KB
subtask2_10.txt AC 20 ms 764 KB
subtask2_11.txt AC 20 ms 764 KB