結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2026-02-19 19:01:05
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 3,347 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 282 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 115,900 KB
最終ジャッジ日時 2026-02-19 19:01:24
合計ジャッジ時間 8,987 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 1 TLE * 4 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# -*- coding: utf-8 -*-

from __future__ import annotations
from dataclasses import dataclass

@dataclass(frozen=True)
class MwfBest:
    """
    Purpose: Represents the best prefix information for the weighted maximum prefix sum.

    Fields:
      value : maximum prefix value
      dx    : length / shift amount (used to compute arg)
      arg   : argmax (smallest arg if tie)
    """
    value: int
    dx: int
    arg: int

@dataclass(frozen=True)
class MwfData:
    """
    Purpose: Represents a data structure for computing weighted maximum prefix sums.

    Fields:
      sum : int
        Total accumulated sum (used for monoid concatenation).
      best : MwfBest | None
        Best prefix information.
        - None means "no valid prefix exists".
    """
    sum: int
    best: MwfBest | None = None

    def __mul__(self, other: "MwfData") -> "MwfData":
        ssum = self.sum + other.sum
        if other.best is None:
            return MwfData(ssum, self.best)
        cand_r = self.sum + other.best.value
        if self.best is None:
            return MwfData(ssum, MwfBest(cand_r, other.best.dx, other.best.arg))
        sdx = self.best.dx + other.best.dx
        cand_l = self.best.value
        arg_l = self.best.arg
        arg_r = self.best.dx + other.best.arg
        if cand_l >= cand_r:
            return MwfData(ssum, MwfBest(cand_l, sdx, arg_l))
        return MwfData(ssum, MwfBest(cand_r, sdx, arg_r))

    def __pow__(self, k: int) -> "MwfData":
        if k == 0:
            # Monoid identity element: sum=0, no valid prefix
            return MwfData(0, None)
        rv = self
        while k > 1 and k % 2 == 0:
            rv = rv * rv
            k //= 2
        pv = rv
        rv = rv * rv
        k //= 2
        while k > 0:
            if k % 2 == 1:
                pv = pv * rv
            rv = rv * rv
            k //= 2
        return pv

def floor_prod(n: int, m: int, a: int, b: int, e: MwfData, x: MwfData, y: MwfData):
    """
    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, suf = e, e
    while True:
        p, a = divmod(a, m)
        x *= (y ** p)
        q, b = divmod(b, m)
        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
        n, m, a, b, c, x, y = c - 1, a, m, m - b - 1 + a, d, y, x

def argmax_weighted_floor(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} (a*i+b*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, MwfBest(0, 1, 0)),
        MwfData(b),
    )
    assert res.best is not None
    return res.best.value, res.best.arg

if __name__ == '__main__':
    import sys
    T = int(sys.stdin.readline())
    for _ in range(T):
        N, M, A, B, C, D = map(int, sys.stdin.readline().split())
        max_val, _argmax = argmax_weighted_floor(N, M, A, B, C, D)
        print(max_val)
0