結果

問題 No.15 カタログショッピング
ユーザー izuru_matsuuraizuru_matsuura
提出日時 2016-11-08 18:11:24
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 37 ms / 5,000 ms
コード長 1,436 bytes
コンパイル時間 1,966 ms
コンパイル使用メモリ 155,264 KB
実行使用メモリ 8,320 KB
最終ジャッジ日時 2024-06-12 04:58:43
合計ジャッジ時間 2,800 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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));
            }
        }
    }
    ans.sort;
    foreach (a; ans) {
        writefln("%(%s %)", a.map!"a + 1".array);
    }

}
0