結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-28 00:59:11
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,564 ms / 2,000 ms
コード長 2,895 bytes
記録
コンパイル時間 843 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 86,920 KB
最終ジャッジ日時 2025-12-03 23:35:38
合計ジャッジ時間 40,908 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Max Weighted Floor (mwf) を求める。
"""


def mwf_par(l: list[int], r: list[int], m: list[int], a: list[int], b: list[int], c: list[int], d: list[int]) -> list[int]:
    """
    mwf を並列計算する。

    各引数は配列で与えられ、同じ長さであることが前提。
    各インデックス i について mwf(l[i], r[i], m[i], a[i], b[i], c[i], d[i]) を計算する。

    計算量: 各ケースについて O(log m)。
    """
    import numpy as np
    assert len(l) == len(r) == len(m) == len(a) == len(b) == len(c) == len(d)
    assert all(0 <= x < y <= 1000000000 for x, y in zip(l, r))
    assert all(0 < x <= 1000000000 for x in m)
    assert all(-1000000000 <= x <= 1000000000 for x in a)
    assert all(-1000000000 <= x <= 1000000000 for x in b)
    assert all(0 <= x < y for x, y in zip(c, m))
    assert all(0 <= x < y for x, y in zip(d, m))
    wl = np.array(l, dtype=np.int64)
    wn = np.array(r, dtype=np.int64) - wl
    wm = np.array(m, dtype=np.int64)
    wa = np.array(a, dtype=np.int64)
    wb = np.array(b, dtype=np.int64)
    wc = np.array(c, dtype=np.int64)
    wd = np.array(d, dtype=np.int64) + wc * wl
    sum_acc = wa * wl + wb * (wd // wm)
    wd %= wm
    max_acc = sum_acc.copy()
    zero = np.zeros_like(wn, dtype=np.int64)
    one = np.ones_like(wn, dtype=np.int64)
    for _ in range(45): # 本問の制約下では十分 : fibonacci(45) > 10^9
        wa += wb * (wc // wm)
        wc %= wm
        sum_acc += wb * (wd // wm)
        wd %= wm
        wn -= 1
        y_max = (wc * wn + wd) // wm
        max_acc = np.maximum(max_acc, np.maximum(sum_acc, sum_acc + wa * wn + wb * y_max))
        terminate = (y_max == 0) | ((wa >= 0) & (wb >= 0)) | ((wa <= 0) & (wb <= 0))
        sum_acc = np.where(wa < 0, sum_acc + (wa + wb), sum_acc)
        sum_acc = np.where(terminate, max_acc, sum_acc)
        wn, wm, wa, wb, wc, wd = (
            np.where(terminate, one, y_max),
            np.where(terminate, one, wc),
            np.where(terminate, zero, wb),
            np.where(terminate, zero, wa),
            np.where(terminate, zero, wm),
            np.where(terminate, zero, (wm - wd - 1)),
        )
    return max_acc.tolist()


def solve():
    """
    入力を受け取り、各ケースについて mwf(N, M, A, B, C, D) を求めて出力します。
    """
    import sys
    input = sys.stdin.readline

    T = int(input())
    
    data = [list(map(int, input().split())) for _ in range(T)]
    result: list[int] = mwf_par(
        [0] * T,
        [row[0] for row in data],
        [row[1] for row in data],
        [row[2] for row in data],
        [row[3] for row in data],
        [row[4] for row in data],
        [row[5] for row in data],
    )
    assert len(result) == T
    for ans in result:
        print(ans)

if __name__ == '__main__':
    solve()
0