結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-03 21:12:46
言語 Nim
(2.2.0)
結果
AC  
実行時間 506 ms / 2,000 ms
コード長 1,190 bytes
記録
コンパイル時間 4,654 ms
コンパイル使用メモリ 67,924 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-03 23:30:40
合計ジャッジ時間 16,381 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std/[strutils, sequtils]

proc mwf(n0, m0, a0, b0, c0, d0: int64): int64 =
  ## Max Weighted Floor (MWF)
  assert n0 > 0 and m0 > 0 and c0 >= 0 and c0 < m0 and d0 >= 0 and d0 < m0
  var n = n0
  var m = m0
  var a = a0
  var b = b0
  var c = c0
  var d = d0

  var sumAcc: int64 = 0
  var maxAcc: int64 = (d div m) * b

  while true:
    var q: int64
    var cand: int64
    (q, c) = (c div m, c mod m)
    a += b * q

    (q, d) = (d div m, d mod m)
    sumAcc += b * q
    if sumAcc > maxAcc:
      maxAcc = sumAcc

    let n1 = n - 1
    let yMax = (c * n1 + d) div m
    if yMax == 0:
      cand = sumAcc + a * n1
      if cand > maxAcc:
        maxAcc = cand
      return maxAcc

    if a >= 0:
      cand = sumAcc + a * n1 + b * yMax
      if cand > maxAcc:
        maxAcc = cand
    else:
      sumAcc += a + b

    n = yMax
    d = m - d - 1
    swap(a, b)
    swap(c, m)

when isMainModule:
  let t = stdin.readLine.parseInt
  for _ in 0..<t:
    let vals = stdin.readLine.split.map(parseInt)
    let (n, m, a, b, c, d) = (vals[0].int64, vals[1].int64, vals[2].int64,
                              vals[3].int64, vals[4].int64, vals[5].int64)
    echo mwf(n, m, a, b, c, d)
0