Submission #855588

---

Source Code Expand

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;
}

Submission Info

Judge Result