Submission #2775054


Source Code Expand

Copy
N = gets.to_i

a_list = gets.strip.split(/ /).collect{|x| x.to_i}


sum = 0
s_list = []
a_list.each{|a|
	sum += a
	s_list << sum
}
#p a_list
#p s_list

l_table = {}
r_table = {}
s_list.each_with_index{|s, i|
	l_table[s] = i
	r_table[sum - s + a_list[i]] = i
}

#p l_table
#p r_table

minimum = sum

(1..(N - 3)).each{|d2|
#	p d2
	
	l_sum = s_list[d2]
	r_sum = sum - l_sum
	
#	p [l_sum, r_sum]
	
	l_sum2 = l_sum / 2
	r_sum2 = r_sum / 2
	
	d1 = (0...d2).bsearch{|i|
		s_list[i] >= l_sum2
	}
	if d1 == nil
		d1 = d2 - 1
	elsif d1 > 0 && (s_list[d1 - 1] * 2 - l_sum).abs < (s_list[d1] * 2 - l_sum).abs
		d1 -= 1
	end
	
	d3 = ((d2 + 1)...(N - 1)).bsearch{|i|
		s_list[i] - l_sum >= r_sum2
	}
	if d3 == nil
		d3 = d2 + 1
	elsif d3 > 0 && ((s_list[d3 - 1] - l_sum) * 2 - r_sum).abs < ((s_list[d3] - l_sum) * 2 - r_sum).abs
		d3 -= 1
	end
	
#	p [d1, d2, d3]
	
	s1 = s_list[d1]
	s4 = sum - s_list[d3]
	pqrs = [s1, l_sum - s1, r_sum - s4, s4]
	
#	p pqrs
	
	diff = pqrs.max - pqrs.min
	if diff < minimum
		minimum = diff
	end
	
}

puts minimum




Submission Info

Submission Time
Task D - Equal Cut
User TakaakiUmedu
Language Ruby (2.3.3)
Score 0
Code Size 1112 Byte
Status WA
Exec Time 1105 ms
Memory 49100 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 3
AC × 40
WA × 3
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt
Case Name Status Exec Time Memory
sample_01.txt AC 7 ms 1788 KB
sample_02.txt AC 7 ms 1788 KB
sample_03.txt AC 7 ms 1788 KB
subtask_1_01.txt AC 7 ms 1788 KB
subtask_1_02.txt AC 1030 ms 46868 KB
subtask_1_03.txt AC 450 ms 22988 KB
subtask_1_04.txt AC 676 ms 30228 KB
subtask_1_05.txt AC 8 ms 1788 KB
subtask_1_06.txt AC 126 ms 7676 KB
subtask_1_07.txt AC 613 ms 27724 KB
subtask_1_08.txt WA 359 ms 20368 KB
subtask_1_09.txt AC 592 ms 27156 KB
subtask_1_10.txt AC 813 ms 34896 KB
subtask_1_11.txt AC 980 ms 44944 KB
subtask_1_12.txt AC 445 ms 23568 KB
subtask_1_13.txt AC 650 ms 28688 KB
subtask_1_14.txt AC 206 ms 11644 KB
subtask_1_15.txt AC 125 ms 7548 KB
subtask_1_16.txt AC 524 ms 25268 KB
subtask_1_17.txt AC 465 ms 23292 KB
subtask_1_18.txt WA 31 ms 3068 KB
subtask_1_19.txt AC 1005 ms 44816 KB
subtask_1_20.txt AC 1022 ms 47508 KB
subtask_1_21.txt AC 521 ms 24848 KB
subtask_1_22.txt AC 334 ms 18836 KB
subtask_1_23.txt AC 872 ms 36268 KB
subtask_1_24.txt AC 1079 ms 48076 KB
subtask_1_25.txt AC 1080 ms 48076 KB
subtask_1_26.txt AC 1046 ms 48076 KB
subtask_1_27.txt AC 1086 ms 48076 KB
subtask_1_28.txt AC 1087 ms 48076 KB
subtask_1_29.txt AC 1095 ms 48076 KB
subtask_1_30.txt AC 1086 ms 48076 KB
subtask_1_31.txt AC 1089 ms 48076 KB
subtask_1_32.txt AC 1098 ms 48020 KB
subtask_1_33.txt AC 1091 ms 48020 KB
subtask_1_34.txt AC 1019 ms 47052 KB
subtask_1_35.txt AC 1105 ms 46996 KB
subtask_1_36.txt WA 991 ms 46996 KB
subtask_1_37.txt AC 1071 ms 49100 KB