結果

問題 No.617 Nafmo、買い出しに行く
コンテスト
ユーザー nanae
提出日時 2018-02-07 17:05:54
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 7 ms / 2,000 ms
コード長 8,566 bytes
コンパイル時間 1,696 ms
コンパイル使用メモリ 140,440 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-12 23:48:24
合計ジャッジ時間 2,162 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array;

void main() {
    int n,k;
    scan(n,k);

    auto bs = BitSet(k + 1);
    bs.set(0);

    foreach (i ; 0 .. n) {
        int ai;
        scan(ai);
        bs |= bs << ai;
    }

    foreach_reverse (i ; 0 .. k + 1) {
        if (bs[i]) {
            writeln(i);
            return;
        }
    }
}


struct BitSet {
    // 64bit符号無し整数によるbitset (64 = 2^6)

    private {
        // _N : 要素数
        // _size : N/64 の切り上げ
        size_t _size, _N;
        ulong[] _data;
    }

    this (size_t N) {
        _N = N;
        _size = (_N + 63) / 64;
        _data = new ulong[](_size);
    }

    // bool[]による初期化
    this (bool[] arr) {
        _N = arr.length;
        _size = (_N + 63) / 64;
        _data = new ulong[](_size);

        foreach (i ; 0 .. arr.length) {
            if (arr[i]) {
                _data[i>>6] |= 1UL << (i&63);
            }
        }
    }

    this (this) {
        _N = _N;
        _size = _size;
        _data = _data.dup;
    }

    // i番目のbitを1にする
    void set(size_t i)
    in {
        assert(0 <= i && i < _N);
    }
    body {
        _data[i>>6] |= 1UL<<(i&63);
    }

    // i番目のbitを0にする
    void reset(size_t i)
    in {
        assert(0 <= i && i < _N);
    }
    body {
        _data[i>>6] &= ~(1UL<<(i&63));
    }

    // i番目のbitを反転させる
    void flip(size_t i)
    in {
        assert(0 <= i && i < _N);
    }
    body {
        _data[i>>6] ^= 1UL<<(i&63);
    }

    // 全てのbitを0にする
    void resetAll() {
        _data[] = 0;
    }

    // popcnt
    size_t popcnt() {
        import core.bitop : _popcnt;
        size_t res;
        foreach (i ; 0 .. _size) {
            res += _popcnt(_data[i]);
        }
        return res;
    }

    // 1となるbitが存在するか判定
    bool any() {
        return popcnt() != 0;
    }

    // 全てのbitが1であるかを判定
    bool all() {
        return popcnt() == _N;
    }

    // &, |, ^
    BitSet opBinary(string op)(const BitSet rhs) 
    in {
        assert(_N == rhs._N);
    }
    body {
        import std.algorithm : min;

        static if (op == "&") {
            auto lhs = this;
            foreach (i ; 0 .. min(lhs._size, rhs._size)) {
                lhs._data[i] &= rhs._data[i];
            }
            return lhs;
        }
        else static if (op == "|") {
            auto lhs = this;
            foreach (i ; 0 .. min(lhs._size, rhs._size)) {
                lhs._data[i] |= rhs._data[i];
            }
            return lhs;
        }
        else static if (op == "^") {
            auto lhs = this;
            foreach (i ; 0 .. min(lhs._size, rhs._size)) {
                lhs._data[i] ^= rhs._data[i];
            }
            return lhs;
        }
    }

    // &=, |=, ^=
    void opOpAssign(string op)(const BitSet rhs) 
    in {
        assert(_N == rhs._N);
    }
    body {
        import std.algorithm : min;

        static if (op == "&") {
            foreach (i ; 0 .. min(_size, rhs._size)) {
                _data[i] &= rhs._data[i];
            }
        }
        else static if (op == "|") {
            foreach (i ; 0 .. min(_size, rhs._size)) {
                _data[i] |= rhs._data[i];
            }
        }
        else static if (op == "^") {
            foreach (i ; 0 .. min(_size, rhs._size)) {
                _data[i] ^= rhs._data[i];
            }
        }
    }

    // <<, >>
    BitSet opBinary(string op)(const size_t offset)
    body {
        static if (op == "<<") {
            auto lhs = this;

            if (offset == 0) {
                return lhs;
            }
            else if (offset >= _N) { // 要素数以上のshiftは全て0に
                lhs.resetAll;
                return lhs;
            }

            auto ofs_arr = offset >> 6;
            auto ofs_bit = offset & 63;

            if (ofs_bit) {
                foreach_reverse (i ; ofs_arr + 1 .. lhs._size) {
                    lhs._data[i] = (lhs._data[i - ofs_arr] << ofs_bit) | (lhs._data[i - ofs_arr - 1] >> (64 - ofs_bit));
                }

                lhs._data[ofs_arr] = lhs._data[0] << ofs_bit;
                lhs._data[0 .. ofs_arr] = 0;
            }
            else {
                foreach_reverse (i ; ofs_arr .. lhs._size) {
                    lhs._data[i] = lhs._data[i - ofs_arr];
                }

                lhs._data[0 .. ofs_arr] = 0;
            }

            // 微妙にあふれたbitを落とす
            lhs._data[$ - 1] &= (~0UL) >> ((lhs._size<<6) - lhs._N);
            
            return lhs;
        }
        else static if (op == ">>") {
            auto lhs = this;

            if (offset == 0) {
                return lhs;
            }
            else if (offset >= _N) {
                lhs.resetAll;
                return lhs;
            }

            auto ofs_arr = offset >> 6;
            auto ofs_bit = offset & 63;

            if (ofs_bit) {
                foreach (i ; 0 .. lhs._size - ofs_arr - 1) {
                    lhs._data[i] = (lhs._data[i + ofs_arr] >> ofs_bit) | (lhs._data[i + ofs_arr + 1] << (64 - ofs_bit));
                }

                lhs._data[lhs._size - ofs_arr - 1] = lhs._data[lhs._size - 1] >> ofs_bit;
                lhs._data[lhs._size - ofs_arr .. $] = 0;
            }
            else {
                foreach (i ; 0 .. lhs._size - ofs_arr) {
                    lhs._data[i] = lhs._data[i + ofs_arr];
                }

                lhs._data[lhs._size - ofs_arr .. $] = 0;
            }

            return lhs;
        }
    }

    // <<=, >>=
    void opOpAssign(string op)(const size_t offset) 
    body {
        static if (op == "<<") {
            if (offset == 0) {
                return;
            }
            else if (offset >= _N) { // 要素数以上のshiftは全て0に
                _data[] = 0;
                return;
            }

            auto ofs_arr = offset >> 6;
            auto ofs_bit = offset & 63;

            if (ofs_bit) {
                foreach_reverse (i ; ofs_arr + 1 .. _size) {
                    _data[i] = (_data[i - ofs_arr] << ofs_bit) | (_data[i - ofs_arr - 1] >> (64 - ofs_bit));
                }

                _data[ofs_arr] = _data[0] << ofs_bit;
                _data[0 .. ofs_arr] = 0;
            }
            else {
                foreach_reverse (i ; ofs_arr .. _size) {
                    _data[i] = _data[i - ofs_arr];
                }

                _data[0 .. ofs_arr] = 0;
            }

            _data[$ - 1] &= (~0UL) >> ((_size<<6) - _N);
        }
        else static if (op == ">>") {
            if (offset == 0) {
                return;
            }
            else if (offset >= _N) {
                _data[] = 0;
                return;
            }

            auto ofs_arr = offset >> 6;
            auto ofs_bit = offset & 63;

            if (ofs_bit) {
                foreach (i ; 0 .. _size - ofs_arr - 1) {
                    _data[i] = (_data[i + ofs_arr] >> ofs_bit) | (_data[i + ofs_arr + 1] << (64 - ofs_bit));
                }

                _data[_size - ofs_arr - 1] = _data[_size - 1] >> ofs_bit;
                _data[_size - ofs_arr .. $] = 0;
            }
            else {
                foreach (i ; 0 .. _size - ofs_arr) {
                    _data[i] = _data[i + ofs_arr];
                }

                _data[_size - ofs_arr .. $] = 0;
            }
        }
    }
    

    bool opIndex(size_t index)
    in {
        assert(0 <= index && index < _N);
    }
    body {
        return !!(_data[index>>6] & (1UL<<(index&63)));
    }

    bool[] array() {
        bool[] res = new bool[](_N);

        foreach (i ; 0 .. _N) {
            res[i] = !!(_data[i>>6] & (1UL << (i&63)));
        }

        return res;
    }

    string toString() {
        import std.format : format;
        return format("[%(%b, %)]", array);
    }
}





void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}
0