Submission #67586675

Source Code Expand

N,M,*X = $<.read.split.map(&:to_i)
X.sort!
D = X.each_cons(2).with_index.map{|(x,y),i|
	(y-x)*N+i
}.sort.reverse
W = (0..(D[0]||0)+1).bsearch{|w|
	# w 以上の距離がある家と家は同じ基地局でカバーしない
	# ⇔距離が w 未満の家と家は同じ基地局でカバーする
	# w が大きくなると必要な基地局が減る
	# 必要な基地局が初めて M 以下になる w を求める
	カバーしない家間の数 = D.bsearch_index{|d| w>d }||N-1
	必要な基地局の数 = カバーしない家間の数+1
	必要な基地局の数<=M or next
}
p D.sum{|d| d<W ? d/N : 0 }

Submission Info

Submission Time
Task D - Transmission Mission
User ds14050
Language Ruby (ruby 3.2.2)
Score 400
Code Size 626 Byte
Status AC
Exec Time 366 ms
Memory 68720 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 18
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt
All 00-sample-01.txt, 00-sample-02.txt, 00-sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 46 ms 17408 KiB
00-sample-02.txt AC 47 ms 17016 KiB
00-sample-03.txt AC 47 ms 17404 KiB
01-01.txt AC 46 ms 17500 KiB
01-02.txt AC 47 ms 17272 KiB
01-03.txt AC 46 ms 17432 KiB
01-04.txt AC 48 ms 17388 KiB
01-05.txt AC 47 ms 17404 KiB
01-06.txt AC 47 ms 17548 KiB
01-07.txt AC 266 ms 64116 KiB
01-08.txt AC 268 ms 64624 KiB
01-09.txt AC 332 ms 63716 KiB
01-10.txt AC 259 ms 68720 KiB
01-11.txt AC 339 ms 63996 KiB
01-12.txt AC 216 ms 48064 KiB
01-13.txt AC 366 ms 63936 KiB
01-14.txt AC 250 ms 62336 KiB
01-15.txt AC 295 ms 64724 KiB