結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2026-02-15 21:45:10
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 1,125 ms / 2,000 ms
コード長 4,154 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 401 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 155,356 KB
最終ジャッジ日時 2026-02-15 21:45:35
合計ジャッジ時間 25,419 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from __future__ import annotations
import sys
from dataclasses import dataclass

LL_MIN = -(1 << 63)


@dataclass(frozen=True)
class MwfData:
    """
    sum : total sum (for concatenation)
    best: maximum prefix value (or LL_MIN meaning "no valid prefix")
    dx  : length / shift amount (used to compute arg)
    arg : argmax (smallest arg if tie)
    """
    sum: int
    best: int = LL_MIN
    dx: int = 0
    arg: int = 0

    def __mul__(self, other: "MwfData") -> "MwfData":
        S_MIN = LL_MIN

        ssum = self.sum + other.sum
        sdx = self.dx + other.dx

        cand_l = self.best
        cand_r = S_MIN if other.best == S_MIN else (self.sum + other.best)

        if cand_l > cand_r:
            return MwfData(ssum, cand_l, sdx, self.arg)
        if cand_l < cand_r:
            return MwfData(ssum, cand_r, sdx, self.dx + other.arg)

        # tie
        if cand_l == S_MIN:
            return MwfData(ssum, S_MIN, sdx, 0)

        return MwfData(ssum, cand_l, sdx, min(self.arg, self.dx + other.arg))

    def __pow__(self, k: int) -> "MwfData":
        # support: x ** k  (k >= 0)
        if not isinstance(k, int):
            return NotImplemented
        assert k >= 0

        if k == 0:
            return MwfData(0)

        S_MIN = LL_MIN
        ssum = self.sum * k
        sdx = self.dx * k

        if self.best == S_MIN:
            return MwfData(ssum, S_MIN, sdx, 0)

        if self.sum > 0:
            sbest = (k - 1) * self.sum + self.best
            sarg = (k - 1) * self.dx + self.arg
            return MwfData(ssum, sbest, sdx, sarg)

        return MwfData(ssum, self.best, sdx, self.arg)

    # Optional: compatibility method
    def pow(self, k: int) -> "MwfData":
        return self ** k


def floor_prod(n: int, m: int, a: int, b: int, e, x, y):
    """
    Generic translation of the C++ template:

    T floor_prod(S n, S m, S a, S b, T e, T x, T y)

    Requires:
      - integers n,m,a,b with 0<=n, 0<m, 0<=a, 0<=b
      - x,y,e are elements of a monoid-like structure:
          * multiplication:  t1 * t2
          * power:           t ** k for k>=0
    """
    assert 0 <= n and 0 < m and 0 <= a and 0 <= b

    c = (a * n + b) // m
    pre = e
    suf = e

    while True:
        p = a // m
        a %= m
        x = x * (y ** p)

        q = b // m
        b %= m
        pre = pre * (y ** q)

        c -= (p * n + q)
        if c == 0:
            return pre * (x ** n) * suf

        d = (m * c - b - 1) // a + 1
        suf = y * (x ** (n - d)) * suf

        b = m - b - 1 + a
        m, a = a, m
        n = c - 1
        c = d
        x, y = y, x


def argmax_weighted_floor_of_linear(n: int, m: int, a: int, b: int, c: int, d: int) -> tuple[int, int]:
    """
    argmwf(n,m,a,b,c,d) = (
      max_{0<=i<n} floor((a*i+b)/m) + floor((c*i+d)/m),
      argmax (smallest i if tie)
    )
    """
    assert n > 0 and m > 0

    res: MwfData = floor_prod(
        n, m, c, d,
        MwfData(0),
        MwfData(a, 0, 1, 0),
        MwfData(b),
    )
    return res.best, res.arg


def max_weighted_floor_of_linear(n: int, m: int, a: int, b: int, c: int, d: int) -> int:
    return argmax_weighted_floor_of_linear(n, m, a, b, c, d)[0]


def mwf_f(x: int, m: int, a: int, b: int, c: int, d: int) -> int:
    # f(x) = a*x + b*floor((c*x + d)/m)
    return a * x + b * ((c * x + d) // m)


def main() -> None:
    it = iter(sys.stdin.buffer.read().split())
    try:
        t = int(next(it))
    except StopIteration:
        return

    out_lines: list[str] = []
    for _ in range(t):
        n = int(next(it)); m = int(next(it))
        a = int(next(it)); b = int(next(it))
        c = int(next(it)); d = int(next(it))
        assert n > 0 and m > 0

        max_val, argmax = argmax_weighted_floor_of_linear(n, m, a, b, c, d)
        # assert 0 <= argmax < n
        # assert mwf_f(argmax, m, a, b, c, d) == max_val
        # assert argmax == 0 or max_weighted_floor_of_linear(argmax, m, a, b, c, d) < max_val

        out_lines.append(str(max_val))

    sys.stdout.write("\n".join(out_lines))


if __name__ == "__main__":
    main()
0