#1182575 (C#) No.3670 Fast Knapsack

• 問題: No.3670 Fast Knapsack
• ユーザー: tobisatis
• 提出日時: 2026-09-04 23:09:55
• 言語: C# (.NET 10.0.400)
• 結果: RE
• 実行時間: -
• コード長: 4,628 bytes
• コンパイル時間: 8,257 ms
• コンパイル使用メモリ: 172,784 KB
• 実行使用メモリ: 82,396 KB
• 最終ジャッジ日時: 2026-09-04 23:10:54
• 合計ジャッジ時間: 14,134 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge6_0

ファイルパターン	結果
sample	AC * 1
other	AC * 1 RE * 1 TLE * 1 -- * 22

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (90 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

#nullable enable

using System.Numerics;

#region

var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

static T[] Range<T>(int n, Func<T> F) => Enumerable.Range(0, n).Select(_ => F()).ToArray();

int Solve()
{
    var n = I<int>();
    var s = I<int>();
    var az = Range(n, I<int>);
    Array.Sort(az);
    var l = 1L;
    var f = false;
    var da = new ExtendedBitArray(1);
    var dd = new HashSet<int>(){ 0 };
    foreach (var a in az)
    {
        l += a;
        if (f) da |= da << a;
        else
        {
            var ndd = new HashSet<int>(dd);
            foreach (var v in dd) ndd.Add(v + a);
            dd = ndd;
            if (dd.Count > 500)
            {
                f = true;
                da = new((int)l);
                foreach (var v in dd) da[v] = true;
            }
        }
    }
    for (var i = Math.Min(s, (int)l); i > 0; i--)
    {
        if (dd.Contains(i)) return i;
        if (f && da[i]) return i;
    }
    return 0;
}

var ans = Range(I<int>(), Solve);
Console.WriteLine(string.Join(Environment.NewLine, ans));

readonly struct ExtendedBitArray : IBitwiseOperators<ExtendedBitArray, ExtendedBitArray, ExtendedBitArray>
{
    const int D = 6;
    const int MD = (1 << D) - 1;
    int Length { get; init; }
    Memory<ulong> Value { get; init; }

    public ExtendedBitArray(int digit)
    {
        Length = (digit + (1 << D) - 1) >> D;
        Value = new ulong[Length];
    }

    public ExtendedBitArray Copy()
    {
        var a = new ulong[Length];
        for (var i = 0; i < Length; i++) a[i] = Value.Span[i];
        return new() { Length = Length, Value = a };
    }

    public int Capacity => Length << D;

    public bool this[int i]
    {
        get => (Value.Span[i >> D] & FlagMD(i)) > 0;
        set
        {
            var span = Value.Span;
            var v = span[i >> D];
            var f = FlagMD(i);
            if (value) v |= f; else v &= ~f;
            span[i >> D] = v;
        }
    }

    public static ExtendedBitArray operator &(ExtendedBitArray l, ExtendedBitArray r)
    {
        if (l.Length > r.Length) (l, r) = (r, l);
        var res = l.Copy();
        var v = res.Value.Span;
        var ov = r.Value.Span;
        for (var i = 0; i < v.Length; i++) v[i] &= ov[i];
        return res;
    }

    public static ExtendedBitArray operator |(ExtendedBitArray l, ExtendedBitArray r)
    {
        if (l.Length > r.Length) (l, r) = (r, l);
        var res = r.Copy();
        var v = res.Value.Span;
        var ov = l.Value.Span;
        for (var i = 0; i < ov.Length; i++) v[i] |= ov[i];
        return res;
    }

    public static ExtendedBitArray operator ^(ExtendedBitArray l, ExtendedBitArray r)
    {
        if (l.Length > r.Length) (l, r) = (r, l);
        var res = r.Copy();
        var v = res.Value.Span;
        var ov = l.Value.Span;
        for (var i = 0; i < ov.Length; i++) v[i] ^= ov[i];
        return res;
    }

    public static ExtendedBitArray operator ~(ExtendedBitArray u)
    {
        var res = u.Copy();
        var v = res.Value.Span;
        for (var i = 0; i < v.Length; i++) v[i] = ~v[i];
        return res;
    }

    public static ExtendedBitArray operator <<(ExtendedBitArray l, int r)
    {
        var (p, s) = (r >> D, r & MD);
        var t = MD + 1 - s;
        var a = new ulong[l.Length + p + 1];
        var sa = a.AsSpan();
        var sl = l.Value.Span;
        for (var i = 0; i < sl.Length; i++)
        {
            sa[i + p] ^= sl[i] << s;
            if (t <= MD) sa[i + p + 1] ^= sl[i] >> t;
        }
        return new(){ Length = sa.Length, Value = a };
    }

    public static ExtendedBitArray operator >>(ExtendedBitArray l, int r)
    {
        var (p, s) = (r >> D, r & MD);
        if (l.Length <= p) return new(){ Length = 0, Value = Array.Empty<ulong>() };
        var t = MD + 1 - s;
        var a = new ulong[l.Length - p];
        var sa = a.AsSpan();
        var sl = l.Value.Span;
        for (var i = 0; i < sa.Length - 1; i++)
        {
            sa[i] ^= sl[i + p] >> s;
            if (t <= MD) sa[i] ^= sl[i + p + 1] << t;
        }
        sa[^1] = sl[sa.Length - 1 + p] >> s;
        return new(){ Length = sa.Length, Value = a };
    }

    public int PopCount()
    {
        var res = 0;
        var span = Value.Span;
        foreach (var d in span) res += BitOperations.PopCount(d);
        return res;
    }

    static ulong FlagMD(int i) => 1UL << (i & MD);
}