#1186183 (C#) No.3711 Udon, Tempura

• 問題: No.3711 Udon, Tempura
• ユーザー: tobisatis
• 提出日時: 2026-09-11 21:48:42
• 言語: C# (.NET 10.0.400 + ACL)
• 結果: AC
• 実行時間: 68 ms / 2,000 ms
• コード長: 3,993 bytes
• コンパイル時間: 10,058 ms
• コンパイル使用メモリ: 172,060 KB
• 実行使用メモリ: 50,300 KB
• 最終ジャッジ日時: 2026-09-11 21:48:56
• 合計ジャッジ時間: 10,003 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 34

コンパイルメッセージ

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

ソースコード

#nullable enable

#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();

var n = I<int>();
var m = I<int>();
var uz = Range(n, I<int>);
var tz = Range(m, I<int>);

var max = uz.Max() + tz.Sum() + 1;
var tb = new ExtendedBitArray(max);
tb[0] = true;
foreach (var t in tz) tb |= tb << t;
var ub = new ExtendedBitArray(max);
foreach (var u in uz) ub |= tb << u;
var ans = ub.PopCount();
Console.WriteLine(ans);

readonly struct 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 += (int)ulong.PopCount(d);
        return res;
    }

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