概要

袋の耐荷重は \(C_{\min}=\min(C_1,\dots,C_M)\) に固定されるので、「重さの合計が \(C_{\min}\) 以下になる連続部分列 \((l,r)\) が何通りあるか」を数える問題です。

考察

まず袋は最小のものしか残っていないため、使える条件は常に $\(W_l+W_{l+1}+\cdots+W_r \le C_{\min}\)\( だけになります。よって \)C{\min}\( を求めたあとは、配列 \)W\( に対して「部分和が \)C{\min}$ 以下の連続区間の個数」を数えればよいです。

素朴に全ての \((l,r)\) を試すと、組は最大で \(N(N+1)/2\) 個あり、\(N\le 5\times 10^5\) では \(O(N^2)\) となって確実にTLEになります。

ここで重要な観察は、\(W_i \ge 1\)（すべて正）であることです。正の数のみの配列では、

• 右端 \(r\) を右に伸ばすと区間和は増える（または同じにはならない）
• 左端 \(l\) を右に縮めると区間和は減る

という単調性があるため、しゃくとり法（Two Pointers / Sliding Window）で全体を \(O(N)\) で数えられます。

具体例として \(W=[2,1,3,2],\ C_{\min}=4\) を考えると、 - \(l=0\) のとき最大まで伸ばすと \([2,1]\)（和3）まで、次に 3 を入れると 6 で超えるので止まる → このとき条件を満たす右端は \(r=0,1\) の2通り - 次に \(l=1\) に進め、同様に「入るだけ右端を伸ばす」を繰り返す
という形で、右端を戻さずに全区間を数えられます。

アルゴリズム

1. 入力から \(C_{\min}=\min(C_1,\dots,C_M)\) を求める。
2. しゃくとり法で、各左端 \(l\) について「条件を満たす最大の右端（の次） \(r\)」を維持する。
   • 変数:
     • l: 左端（ループで 0 から \(N-1\)）
     • r: 右端の“次”の位置（半開区間 \([l,r)\) を考える）
     • s: 現在の区間和 \(W_l+\cdots+W_{r-1}\)
   • 手順:
     1. while r < N and s + W[r] <= Cmin: の間、r を進めて s に加える（入るだけ伸ばす）。
     2. このとき固定した l に対して条件を満たす区間は
        $\([l,l], [l,l+1], \dots, [l,r-1]\)\( の **\)(r-l)$ 通り**なので、答えに r - l を加える。
     3. 次の l+1 に移るために、通常は s -= W[l] で左端を1つ外す。
     4. ただし r == l（つまり長さ0で、\(W_l\) すら入らない）場合、s を引くものがないので、r を1つ進めて詰まらないようにする（コードの if r == l: r += 1）。

この方法では r は全体で高々 \(N\) 回しか増えないため、全体が線形時間で動きます。

計算量

• 時間計算量: \(O(N+M)\)（\(C_{\min}\) の計算が \(O(M)\)、しゃくとり法が \(O(N)\)）
• 空間計算量: \(O(N)\)（重さ配列 \(W\) を保持）

実装のポイント

• \(W_i\) が大きく \(C_{\min}\) は最大 \(10^{18}\) なので、区間和 s は 64bit 相当が必要（Pythonなら自然にOK）。

• 答えの最大値は \(N(N+1)/2\) で \(N=5\times 10^5\) のとき約 \(1.25\times 10^{11}\) になるため、これも 64bit 相当が必要（PythonならOK）。

• r == l のケース（単体でも入らない、つまり \(W_l > C_{\min}\)）を処理しないと、l だけ進んで r が止まり続けてしまうため、コードのように r を進めてループが前に進むようにします。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    W = [next(it) for _ in range(N)]
    Cmin = min(next(it) for _ in range(M))

    r = 0
    s = 0
    ans = 0

    for l in range(N):
        while r < N and s + W[r] <= Cmin:
            s += W[r]
            r += 1
        ans += r - l
        if r == l:
            r += 1
        else:
            s -= W[l]

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。