Submission #2775439


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

#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 994 Byte
Status WA
Exec Time 965 ms
Memory 24084 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 8 ms 1788 KB
subtask_1_01.txt AC 7 ms 1788 KB
subtask_1_02.txt AC 877 ms 23316 KB
subtask_1_03.txt AC 406 ms 11852 KB
subtask_1_04.txt AC 591 ms 14096 KB
subtask_1_05.txt AC 8 ms 1788 KB
subtask_1_06.txt AC 112 ms 4600 KB
subtask_1_07.txt AC 538 ms 12816 KB
subtask_1_08.txt WA 315 ms 10896 KB
subtask_1_09.txt AC 522 ms 12816 KB
subtask_1_10.txt AC 709 ms 19600 KB
subtask_1_11.txt AC 853 ms 21780 KB
subtask_1_12.txt AC 384 ms 11920 KB
subtask_1_13.txt AC 571 ms 13072 KB
subtask_1_14.txt AC 181 ms 6652 KB
subtask_1_15.txt AC 110 ms 4476 KB
subtask_1_16.txt AC 460 ms 11828 KB
subtask_1_17.txt AC 412 ms 11516 KB
subtask_1_18.txt WA 29 ms 2300 KB
subtask_1_19.txt AC 879 ms 20684 KB
subtask_1_20.txt AC 883 ms 23444 KB
subtask_1_21.txt AC 450 ms 12308 KB
subtask_1_22.txt AC 289 ms 10900 KB
subtask_1_23.txt AC 775 ms 20244 KB
subtask_1_24.txt AC 909 ms 22036 KB
subtask_1_25.txt AC 920 ms 24084 KB
subtask_1_26.txt AC 912 ms 22092 KB
subtask_1_27.txt AC 938 ms 22036 KB
subtask_1_28.txt AC 957 ms 22092 KB
subtask_1_29.txt AC 960 ms 22092 KB
subtask_1_30.txt AC 965 ms 22092 KB
subtask_1_31.txt AC 945 ms 22092 KB
subtask_1_32.txt AC 965 ms 22092 KB
subtask_1_33.txt AC 958 ms 22092 KB
subtask_1_34.txt AC 898 ms 20940 KB
subtask_1_35.txt AC 942 ms 20940 KB
subtask_1_36.txt WA 907 ms 20940 KB
subtask_1_37.txt AC 950 ms 20940 KB