Submission #35932327

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import qualified Data.IntMap as M
-- import Data.Ratio
main = do
  [n,a] <- bsGetLnInts
  wxvs <- replicateM n bsGetLnInts
  let ans = abc274f n a wxvs
  print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)
abc274f :: Int -> Int -> [[Int]] -> Int
abc274f n a wxvs = maximum $ map (score a wxvs) wxvs
score a wxvs (wi:xi:vi:_) =
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import qualified Data.IntMap as M
-- import Data.Ratio

main = do
  [n,a] <- bsGetLnInts
  wxvs <- replicateM n bsGetLnInts
  let ans = abc274f n a wxvs
  print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)

abc274f :: Int -> Int -> [[Int]] -> Int
abc274f n a wxvs = maximum $ map (score a wxvs) wxvs

score a wxvs (wi:xi:vi:_) =
--    maximum $ loop 0 $ M.assocs twm
    maximum $ map snd $ dropWhile ((0 >) . fst) $ scanl1 add $ M.assocs twm
  where
    twm = M.fromListWith (+) -- addp
          [ tw
          | (wj:xj:vj:_) <- wxvs
          , tw <- spike (vj - vi) (xj - xi) wj
          ]
    spike uj yj wj =
      case compare uj 0 of
        LT -> [(ta, wj), (succ t0, -wj)]
        EQ -> [(0 % 1, wj) | 0 <= yj, yj <= a]
        GT -> [(t0, wj), (succ ta, -wj)]
      where
        m1 = -1 % 1
        t0 = let t = (0 - yj) % uj in if t < 0 then m1 else t
        ta = let t = (a - yj) % uj in if t < 0 then m1 else t
    add (_,acc) (t,d) = let acc1 = acc + d in acc1 `seq` (t, acc1)
--    addp (a,b) (c,d) = (a+c, b+d)
{-
    loop _ [] = []
    loop acc ((t, (wp,wm)):twms)
      | t < 0 =        loop acc2 twms
      | True  = acc1 : loop acc2 twms
      where
        acc1 = acc  + wp
        acc2 = acc1 - wm
-}
-- (%) :: Int -> Int -> Double
-- m % n = fromIntegral m / fromIntegral n

(%) :: Int -> Int -> Int
m % n = div (10^9 * m) n

-- IntMap delta=succ

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result