結果

問題 No.15 カタログショッピング
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-11-08 18:08:24
言語 D
(dmd 2.105.2)
結果
WA  
実行時間 -
コード長 1,436 bytes
コンパイル時間 1,720 ms
コンパイル使用メモリ 157,480 KB
実行使用メモリ 10,996 KB
最終ジャッジ日時 2023-09-02 22:47:32
合計ジャッジ時間 2,649 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,368 KB
testcase_01 AC 2 ms
4,368 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,368 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff #

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) {
    stderr.writeln(arg);
}
int size(T)(in T s) {
    return cast(int)s.length;
}

void main() {
    int N, S; readf("%d %d\n", &N, &S);
    auto P = new int[N];
    foreach (ref p; P) {
        readf("%d\n", &p);
    }

    int L = N / 2;
    int K = N - L;
    int[][int] X;
    for (int bit = 0; bit < (1<<K); bit++) {
        int sum = 0;
        foreach (i; 0 .. K) {
            if (bit & (1<<i)) {
                sum += P[i + L];
            }
        }
        X[sum] ~= bit;
    }

    int[] f(int bit) {
        int[] ret;
        foreach (i; 0 .. N) {
            if (bit & (1 << i)) {
                ret ~= i;
            }
        }
        //stderr.writefln("f : %b %s", bit, ret);
        return ret;
    }

    int[][] ans;
    for (int bit = 0; bit < (1<<L); bit++) {
        int sum = 0;
        foreach (i; 0 .. L) {
            if (bit & (1<<i)) {
                sum += P[i];
            }
        }
        if (S - sum in X) {
            foreach (e; X[S - sum]) {
                assert( (bit & (e<<L)) == 0 );
                ans ~= f(bit + (e<<L));
            }
        }
    }
    foreach (a; ans) {
        writefln("%(%s %)", a.map!"a + 1".array);
    }
    ans.sort;

}
0