Submission #48030855

---

Source Code Expand

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

main :: IO ()
main = do
  [n,k] <- bsGetLnInts
  xys <- replicateM n bsGetLnInts
  let ans = abc330f n k xys
  print ans

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

abc330f :: Int -> Int -> [[Int]] -> Int
abc330f n k xys = sat
  where
    xs = sort $ map head xys
    ys = sort $ map (!! 1) xys
    (_unsat, sat) = binarySearch (\r -> cost xs r + cost ys r <= k) (-1) 1_000_000_001 

    cost as s = sum $ map f as
      where
        l = (!! pred n) $ merge as $ map (subtract s) as
        f a
          | a <= l     = l - a
          | l + s <= a = a - l - s
          | True       = 0

merge xxs@(x:xs) yys@(y:ys) =
  case compare x y of
    LT -> x : merge xs yys
    GT -> y : merge xxs ys
    EQ -> x : y : merge xs ys
merge xs [] = xs
merge [] ys = ys

-- @gotoki_no_joe
binarySearch :: (Int -> Bool) -> Int -> Int -> (Int, Int)
binarySearch prop unsat sat = loop unsat sat
  where
    loop a b
      | ende   = (a, b)
      | prop m = loop a m
      | True   = loop m b
      where
        ende = a == m || b == m 
        m = div (a + b) 2

{-
解説
https://atcoder.jp/contests/abc330/editorial/7774
を写経する。

「数値列 x1, ..., xN を閉区間 [L,L+S] に移動させる最小コストを求めよ」という問題が解けると、
正方形の大きさ S に対するコストが導けるので、二分探索で答えが得られる、という後半は同じ。

「」の問題は、Lの選択がミソで、それは x1, ..., xN, x1-S, ..., xN-S の中央値ふたつの間、なのでN個めの値でよい。
（なんで？ある一点に集めるときには、重心が最適になるのは直観的にわかる。引っ張り合いをして安定するのがそこだから。
それに幅ができたようなものなのか。）
これは、マージソートのマージを使うとO(N)で計算できる。
-}

Submission Info

Compile Error

app/Main.hs:31:1: warning: [-Wmissing-signatures]
    Top-level binding with no type signature:
      merge :: Ord a => [a] -> [a] -> [a]
   |
31 | merge xxs@(x:xs) yys@(y:ys) =
   | ^^^^^

Judge Result