Submission #21839329

Source Code Expand

N = int(input())
A = list(map(int, input().split()))
ansl = max(A[i] + A[i + N] for i in range(N)) - 1
ansr = max(A) * 2
while ansr - ansl > 1:
	X = (ansl + ansr) // 2
	L = []
	R = []
	for i in range(N):
		L.append(A[i])
		R.append(X - A[i + N])
	l = L[0]
	r = R[0] + 1
	while r - l > 1:
		m = (l + r) // 2
		lcur = 0
		rcur = m
		for i in range(N):
			if rcur - lcur > R[i]:
				lcur = rcur - R[i]
			elif rcur - lcur < L[i]:
				rcur = lcur + L[i]
		if rcur <= X:
			l = m
		else:
			r = m
	plcur = 0
	prcur = l
	for i in range(N):
		if prcur - plcur > R[i]:
			plcur = prcur - R[i]
		elif prcur - plcur < L[i]:
			prcur = plcur + L[i]
	if prcur <= X and plcur <= l:
		ansr = X
	else:
		ansl = X
print(ansr)

Submission Info

Submission Time
Task F - Gateau
User square1001
Language PyPy3 (7.3.0)
Score 900
Code Size 746 Byte
Status AC
Exec Time 719 ms
Memory 166316 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 5
AC × 45
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All corner_01.txt, corner_02.txt, corner_03.txt, corner_04.txt, corner_05.txt, corner_06.txt, corner_07.txt, corner_08.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in30.txt, in31.txt, in32.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
Case Name Status Exec Time Memory
corner_01.txt AC 66 ms 61924 KiB
corner_02.txt AC 56 ms 62204 KiB
corner_03.txt AC 54 ms 62032 KiB
corner_04.txt AC 51 ms 61992 KiB
corner_05.txt AC 51 ms 62004 KiB
corner_06.txt AC 59 ms 67540 KiB
corner_07.txt AC 63 ms 67656 KiB
corner_08.txt AC 64 ms 67852 KiB
in01.txt AC 65 ms 68172 KiB
in02.txt AC 256 ms 121600 KiB
in03.txt AC 350 ms 163168 KiB
in04.txt AC 428 ms 163248 KiB
in05.txt AC 68 ms 68036 KiB
in06.txt AC 321 ms 160088 KiB
in07.txt AC 330 ms 149052 KiB
in08.txt AC 69 ms 68000 KiB
in09.txt AC 93 ms 69128 KiB
in10.txt AC 411 ms 149396 KiB
in11.txt AC 488 ms 161932 KiB
in12.txt AC 513 ms 159476 KiB
in13.txt AC 719 ms 165008 KiB
in14.txt AC 658 ms 164600 KiB
in15.txt AC 429 ms 142480 KiB
in16.txt AC 538 ms 166280 KiB
in17.txt AC 578 ms 166144 KiB
in18.txt AC 258 ms 115776 KiB
in19.txt AC 393 ms 163060 KiB
in20.txt AC 391 ms 162828 KiB
in21.txt AC 313 ms 139884 KiB
in22.txt AC 386 ms 162576 KiB
in23.txt AC 391 ms 162688 KiB
in24.txt AC 360 ms 148192 KiB
in25.txt AC 421 ms 159524 KiB
in26.txt AC 422 ms 160276 KiB
in27.txt AC 354 ms 143060 KiB
in28.txt AC 419 ms 164640 KiB
in29.txt AC 279 ms 108960 KiB
in30.txt AC 446 ms 166316 KiB
in31.txt AC 102 ms 93420 KiB
in32.txt AC 89 ms 91740 KiB
sample_01.txt AC 46 ms 62120 KiB
sample_02.txt AC 53 ms 62124 KiB
sample_03.txt AC 45 ms 61756 KiB
sample_04.txt AC 55 ms 61960 KiB
sample_05.txt AC 63 ms 67544 KiB