結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-13 00:06:23
言語 Haskell
(9.10.1)
結果
AC  
実行時間 919 ms / 2,000 ms
コード長 3,369 bytes
記録
コンパイル時間 5,016 ms
コンパイル使用メモリ 206,120 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2025-12-03 23:31:57
合計ジャッジ時間 16,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.10.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff #
raw source code 

{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O2 #-}

module Main where

import Data.Maybe (fromJust)
import qualified Data.ByteString.Char8 as BS
import Control.Monad  (replicateM, replicateM_)

tuplify2 (x:y:_) = (x,y)
tuplify2 _ = undefined

--Input functions with ByteString
readInt = fst . fromJust . BS.readInteger
readIntTuple = tuplify2 . map readInt . BS.words
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntNList n = map readIntList <$> replicateM (fromIntegral n) BS.getLine
getIntMatrix = map readIntList . BS.lines <$> BS.getContents
getIntTuple = readIntTuple <$> BS.getLine
getIntNTuples n = map readIntTuple <$> replicateM (fromIntegral n) BS.getLine
getIntTuples = map readIntTuple . BS.lines <$> BS.getContents

{-|
Max Weighted Floor (mwf)
  mwf(n,m,a,b,c,d) = max_{0 <= x < n} a*x + b*floor((c*x + d)/m)
を返す非再帰（反復）実装。

前提:
  - n > 0, m > 0

計算量/メモリ:
  - 時間: O(log m)（ユークリッド互除法的再帰による構造縮約）
  - 追加メモリ: O(1)
-}
mwf :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer -> Integer
mwf n0 m0 a0 b0 c0 d0 =
  let !sum0 = 0
      !max0 = b0 * (d0 `div` m0)     -- x = 0 のとき
  in go n0 m0 a0 b0 c0 d0 sum0 max0
  where
    go :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer
       -> Integer -> Integer -> Integer
    go !n !m !a !b !c !d !sumacc !maxacc =
      -- 正規化（c,d を 0..m-1 に）
      let (qc, c') = c `divMod` m
          !a'      = a + b * qc
          (qd, d') = d `divMod` m
          !sumacc'      = sumacc + b * qd
          !maxacc'      = max maxacc sumacc'
          -- y_max = max_{0<=x<n} floor((c'*x+d')/m)
          !ymax    = (c' * (n - 1) + d') `div` m
      in
        if ymax == 0
          -- y_max == 0 なら右端だけ見ればよい
          then max maxacc' (sumacc' + a' * (n - 1))
        else
          if a' >= 0
            then
              -- a' >= 0 のときは右端 + b*ymax も候補
              let !maxacc'' = max maxacc' (sumacc' + a' * (n - 1) + b * ymax)
              in if b >= 0
                   -- a' >= 0 かつ b >= 0 なら右端で確定
                   then maxacc''
                   -- 続行（ユークリッド縮約）
                   else go ymax c' b a' m (m - d' - 1) sumacc' maxacc''
          else
            -- a' < 0 のとき
            if b <= 0
              -- どちらも非正→これ以上増えない
              then maxacc'
              -- 続行（ユークリッド縮約）。sum は a'+b を加算
              else go ymax c' b a' m (m - d' - 1) (sumacc' + a' + b) maxacc'

{-|
max_{l <= x < r} a*x + b*floor((c*x + d)/m) を返す。

既存の mwf(n,m,...)（0 <= x < n）を用いる。
前提: l < r, m > 0
-}
mwfLr :: Integer -> Integer -> Integer -> Integer -> Integer -> Integer -> Integer -> Integer
mwfLr l r m a b c d
  | l >= r || m <= 0 = error "mwfLR: require l < r and m > 0"
  | otherwise =
      let n        = r - l
          (q, d')  = (c * l + d) `divMod` m
      in a * l + b * q + mwf n m a b c d'

{-|
入出力（複数ケース）
-}
solve :: IO ()
solve = do
  t <- getInt
  replicateM_ (fromIntegral t :: Int) $ do
    [n, m, a, b, c, d] <- getIntList
    print (mwf n m a b c d)

main :: IO ()
main = solve
0