Submission #47948117

Source Code Expand

(N,K),*XY = $<.map{|ln| ln.split.map(&:to_i) }
X5,Y5 = XY.transpose.map{|xs|
	xs = xs.sort
	rs = xs.reverse
	sl,sr = [xs,rs].map{|xs|
		xs.inject([0]){|s,x| s<<s[-1]+x }
	}
	next xs,sl,rs,sr,rs[0]-xs[0]
}
F = lambda{|xs,sl,rs,sr,_,e,k|
	kx = -1
	j = -xs.size
	xs.each_with_index{|l,i|
		lk = l*i-sl[i]
		break if k-lk<=kx
		r = l+e
		j += 1 while j<0&&xs[j]<=r
		rk = r*j+sr[-j]
		kx = [k-lk-rk,kx].max
	}
	j = -rs.size
	rs.each_with_index{|r,i|
		rk = sr[i]-r*i
		break if k-rk<=kx
		l = r-e
		j += 1 while j<0&&l<=rs[j]
		lk = -sl[-j]-l*j
		kx = [k-rk-lk,kx].max
	}
	next kx
}
p (0..[X5[4],Y5[4]].max).bsearch{|e|
	0<=F[*Y5,e,F[*X5,e,K]]
}

Submission Info

Submission Time
Task F - Minimize Bounding Square
User ds14050
Language Ruby (ruby 3.2.2)
Score 525
Code Size 676 Byte
Status AC
Exec Time 2067 ms
Memory 52200 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 525 / 525
Status
AC × 3
AC × 104
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hack_01.txt, hack_02.txt, hack_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt, test_60.txt, test_61.txt, test_62.txt, test_63.txt, test_64.txt, test_65.txt, test_66.txt, test_67.txt, test_68.txt, test_69.txt, test_70.txt, test_71.txt, test_72.txt, test_73.txt, test_74.txt, test_75.txt, test_76.txt, test_77.txt, test_78.txt, test_79.txt, test_80.txt, test_81.txt, test_82.txt, test_83.txt, test_84.txt, test_85.txt, test_86.txt, test_87.txt, test_88.txt, test_89.txt, test_90.txt, test_91.txt, test_92.txt, test_93.txt, test_94.txt, test_95.txt, test_96.txt, test_97.txt, test_98.txt
Case Name Status Exec Time Memory
hack_01.txt AC 838 ms 51592 KiB
hack_02.txt AC 865 ms 51652 KiB
hack_03.txt AC 883 ms 50436 KiB
sample_01.txt AC 46 ms 17352 KiB
sample_02.txt AC 49 ms 17108 KiB
sample_03.txt AC 47 ms 17576 KiB
test_01.txt AC 46 ms 17212 KiB
test_02.txt AC 46 ms 17164 KiB
test_03.txt AC 47 ms 17304 KiB
test_04.txt AC 47 ms 17612 KiB
test_05.txt AC 48 ms 17452 KiB
test_06.txt AC 48 ms 17436 KiB
test_07.txt AC 47 ms 17224 KiB
test_08.txt AC 47 ms 17228 KiB
test_09.txt AC 48 ms 17504 KiB
test_10.txt AC 46 ms 17248 KiB
test_11.txt AC 48 ms 17492 KiB
test_12.txt AC 47 ms 17608 KiB
test_13.txt AC 49 ms 17512 KiB
test_14.txt AC 49 ms 17548 KiB
test_15.txt AC 49 ms 17536 KiB
test_16.txt AC 49 ms 17588 KiB
test_17.txt AC 50 ms 17492 KiB
test_18.txt AC 49 ms 17500 KiB
test_19.txt AC 49 ms 17384 KiB
test_20.txt AC 50 ms 17440 KiB
test_21.txt AC 49 ms 17472 KiB
test_22.txt AC 49 ms 17500 KiB
test_23.txt AC 50 ms 17396 KiB
test_24.txt AC 49 ms 17580 KiB
test_25.txt AC 49 ms 17448 KiB
test_26.txt AC 49 ms 17500 KiB
test_27.txt AC 1965 ms 49204 KiB
test_28.txt AC 97 ms 18136 KiB
test_29.txt AC 563 ms 25280 KiB
test_30.txt AC 2016 ms 49936 KiB
test_31.txt AC 1728 ms 44488 KiB
test_32.txt AC 530 ms 49480 KiB
test_33.txt AC 1551 ms 49844 KiB
test_34.txt AC 651 ms 34640 KiB
test_35.txt AC 2027 ms 49272 KiB
test_36.txt AC 743 ms 49900 KiB
test_37.txt AC 1634 ms 42780 KiB
test_38.txt AC 1445 ms 40796 KiB
test_39.txt AC 2021 ms 49896 KiB
test_40.txt AC 163 ms 24512 KiB
test_41.txt AC 120 ms 19284 KiB
test_42.txt AC 1903 ms 49860 KiB
test_43.txt AC 1753 ms 48356 KiB
test_44.txt AC 141 ms 20444 KiB
test_45.txt AC 1984 ms 49872 KiB
test_46.txt AC 1579 ms 42652 KiB
test_47.txt AC 282 ms 21264 KiB
test_48.txt AC 553 ms 49916 KiB
test_49.txt AC 860 ms 40332 KiB
test_50.txt AC 187 ms 19524 KiB
test_51.txt AC 1678 ms 48984 KiB
test_52.txt AC 1233 ms 49376 KiB
test_53.txt AC 1432 ms 41148 KiB
test_54.txt AC 2067 ms 49872 KiB
test_55.txt AC 1452 ms 40140 KiB
test_56.txt AC 528 ms 47244 KiB
test_57.txt AC 1562 ms 50320 KiB
test_58.txt AC 628 ms 33720 KiB
test_59.txt AC 1481 ms 41156 KiB
test_60.txt AC 1995 ms 49852 KiB
test_61.txt AC 1518 ms 41824 KiB
test_62.txt AC 1740 ms 44820 KiB
test_63.txt AC 2038 ms 49888 KiB
test_64.txt AC 409 ms 41924 KiB
test_65.txt AC 670 ms 33028 KiB
test_66.txt AC 1464 ms 49672 KiB
test_67.txt AC 1037 ms 34496 KiB
test_68.txt AC 811 ms 29912 KiB
test_69.txt AC 2045 ms 49832 KiB
test_70.txt AC 673 ms 42156 KiB
test_71.txt AC 1497 ms 40804 KiB
test_72.txt AC 530 ms 49048 KiB
test_73.txt AC 313 ms 23980 KiB
test_74.txt AC 135 ms 19960 KiB
test_75.txt AC 316 ms 49876 KiB
test_76.txt AC 313 ms 49884 KiB
test_77.txt AC 1396 ms 51112 KiB
test_78.txt AC 1405 ms 50396 KiB
test_79.txt AC 1406 ms 51200 KiB
test_80.txt AC 1401 ms 51500 KiB
test_81.txt AC 1417 ms 52200 KiB
test_82.txt AC 1388 ms 51476 KiB
test_83.txt AC 1074 ms 48912 KiB
test_84.txt AC 1208 ms 49720 KiB
test_85.txt AC 1228 ms 49168 KiB
test_86.txt AC 1249 ms 49888 KiB
test_87.txt AC 1225 ms 49504 KiB
test_88.txt AC 566 ms 49980 KiB
test_89.txt AC 902 ms 48852 KiB
test_90.txt AC 1206 ms 49832 KiB
test_91.txt AC 1205 ms 49852 KiB
test_92.txt AC 1228 ms 49832 KiB
test_93.txt AC 1232 ms 48724 KiB
test_94.txt AC 1223 ms 49940 KiB
test_95.txt AC 1229 ms 49828 KiB
test_96.txt AC 497 ms 49944 KiB
test_97.txt AC 696 ms 49872 KiB
test_98.txt AC 693 ms 50416 KiB