Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

 バームクーヘン(Baumkuchen)

JOI 君は妹のJOI 子ちゃんとJOI 美ちゃんと一緒におやつを食べようとしている．今日のおやつは3 人の大好物のバームクーヘンだ．

バームクーヘンは下図のような円筒形のお菓子である．3 人に分けるために，JOI 君は半径方向に刃を3回入れて，これを3 つのピースに切り分けなければならない．ただしこのバームクーヘンは本物の木材のように固いので，刃を入れるのは簡単ではない．そのためこのバームクーヘンにはあらかじめ $N$ 個の切れ込みが入っており，JOI 君は切れ込みのある位置でのみ切ることができる．切れ込みに1 から $N$ まで時計回りに番号をふったとき，$1 \leq i \leq N - 1$ に対し， $i$ 番目の切れ込みと$i + 1$ 番目の切れ込みの間の部分の大きさは $A_i$ である．また $N$ 番目の切れ込みと1 番目の切れ込みの間の部分の大きさは $A_N$ である．

図1: バームクーヘンの例 $N = 6, A_1 = 1, A_2 = 5, A_3 = 4, A_4 = 5, A_5 = 2, A_6 = 4$

課題

切れ込みの個数 $N$ と，各部分の大きさを表す整数 $A_1,...,A_N$ が与えられる．バームクーヘンを3 つに切り分けたときの，最も小さいピースの大きさの最大値を出力するプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

 1 行目には，整数 $N$ が書かれている．これはバームクーヘンに $N$ 個の切れ込みがあることを表す．

 続く$N$ 行のうちの $i$ 行目$(1 \leq i \leq N)$ には，整数 $A_i$ が書かれている．これは $i$ 番目の切れ込みと $i + 1$ 番目の切れ込みの間の部分 ($i = N$ のときは $N$ 番目の切れ込みと1 番目の切れ込みの間の部分) の大きさが $A_i$ であることを表す．

出力

標準出力に，バームクーヘンを3 つに切り分けたときの，最も小さいピースの大きさの最大値を表す整数を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

$3 \leq N \leq 100000$

$1 \leq A_i \leq 1000000000 (1 \leq i \leq N)$

入出力例

  
入力例 1 
  

  

6
1
5
4
5
2
4

  
出力例 1 
  

  

6

図2: 1 番目の切れ込みと3 番目の切れ込みと5 番目の切れ込みで切るのが最善である．

  
入力例 2 
  

  

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

  
出力例 2 
  

  

213

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
6
1
5
4
5
2
4


Sample output:
6

Submission status: Accepted

Solution code:
def solve():
    p0, p1, p2 = 0, 1, 2
    best = 1
    succ = True
    while p0 < N-1:
        if not succ:
            p0 += 1
            while d[p2]- d[p1] > d[p1]- d[p0]:
                p2 -= 1

        succ = False

        while p1 - p0 < N - 1 and d[p1] - d[p0] <= best:
            p1 += 1
        d0 = d[p1] - d[p0]
        if d0 <= best:
            continue

        while p2 - p0 < N and d[p2] - d[p1] < d0:
            p2 += 1
        if d[p2] - d[p1] < d0:
            continue

        if L - (d[p2] - d[p0]) >= d0:
            best = d0
            if best >= L//3:
                return best
            succ = True

    return best

N = int(input())
A = [0] * N
L = 0
for i in range(N):
    A[i] = int(input())
    L += A[i]
d = [0] * (2*N)
for i in range(1, 2*N):
    d[i] = d[i-1] + A[(i-1)%N]

print(solve())

Submission status: Accepted

Solution code:
def solve():
    p0, p1, p2 = 0, 1, 2
    best = 1
    succ = True
    while p0 < N-1:
        if not succ:
            p0 += 1
            while d[p2]- d[p1] > d[p1]- d[p0]:
                p2 -= 1

        succ = False

        while p1 - p0 < N - 1 and d[p1] - d[p0] <= best:
            p1 += 1
        d0 = d[p1] - d[p0]
        if d0 <= best:
            continue

        while p2 - p0 < N and d[p2] - d[p1] < d0:
            p2 += 1
        if d[p2] - d[p1] < d0:
            continue

        if L - (d[p2] - d[p0]) >= d0:
            best = d0
            if best >= L//3:
                return best
            succ = True

    return best

N = int(input())
A = [int(input()) for i in range(N)]
L = sum(A)
d = [0] * (2 * N)
for i in range(1, 2 * N):
    d[i] = d[i-1] + A[(i-1)%N]

print(solve())

Submission status: Accepted

Solution code:
# AOJ 0600 Baumkuchen
# Python3 2018.7.3 bal4u

import sys
from sys import stdin
input = stdin.readline

n = int(input())
a = [int(input()) for i in range(n)]
su = sum(a)
p = [0]*(n+1)
s = [0]*(n+1)
l, r = 0, su+1
while l + 1 < r:
	m = (l+r) >> 1
	for i in range(0, n):
		if i == 0: s[i] = p[i] = 0
		else:
			p[i] = p[i-1] - 1
			s[i] = s[i-1] - a[i-1]
			
		while s[i] < m:
			ii = i + p[i];
			if ii >= n: ii -= n
			s[i] += a[ii]
			p[i] += 1

	f = 0	
	for i in range(n):
		ii = i + p[i];
		if ii >= n: ii -= n
		if su-s[i]-s[ii] >= m:
			f = 1
			break
	if f: l = m
	else: r = m
print(l)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
total = sum(A)
A = A + A

def check(next_piece, piece_size):
    for i in range(N):
        ni = next_piece[i]
        if ni == -1: continue
        if piece_size[i] >= total: continue

        ni %= N
        nni = next_piece[ni]
        if nni == -1: continue
        if total - piece_size[i] - piece_size[ni] >= mid:
            return True
    return False

def tow_pointers(mid):
    # しゃくとり法でインデックスの左側を全探索しつつ、合計がmid以上になる最小区間がどこまでかを求める
    # next_piece[i] := iから計算した合計がmid以上になる最小区間の終端インデックス
    # piece_size[i] := iから計算した合計がmid以上になる最小区間の終端インデックスまでの合計値
    next_piece = [-1] * N
    piece_size = [-1] * N
    right, amount = 0, 0
    for left in range(N):
        while right < N * 2 and amount < mid:
            amount += A[right]
            right += 1
        if amount >= mid:
            # amoutがmid以上の場合、それぞれの記録用配列に値を格納する
            next_piece[left] = right
            piece_size[left] = amount
        # ここの役割がわかんね、両方共なんだか必要に見えなくもない
        amount -= A[left]
    return next_piece, piece_size

# 二部探索
low, high = 0, 1 << 60
while high - low > 1:
    mid = low + (high - low) // 2
    next_piece, piece_size = tow_pointers(mid)
    if check(next_piece, piece_size):
        low = mid
    else:
        high = mid

print(low)

Submission status: Accepted

Solution code:
# AOJ 0600 Baumkuchen
# Python3 2018.7.3 bal4u
  
import sys
from sys import stdin
input = stdin.readline
  
n = int(input())
a = [int(input()) for i in range(n)]
su = sum(a)
p = [0]*(n+1)
s = [0]*(n+1)
l, r = 0, su+1
while l + 1 < r:
    m = (l+r) >> 1
    for i in range(0, n):
        if i == 0: s[i] = p[i] = 0
        else:
            p[i] = p[i-1] - 1
            s[i] = s[i-1] - a[i-1]
              
        while s[i] < m:
            ii = i + p[i];
            if ii >= n: ii -= n
            s[i] += a[ii]
            p[i] += 1
  
    f = 0   
    for i in range(n):
        ii = i + p[i];
        if ii >= n: ii -= n
        if su-s[i]-s[ii] >= m:
            f = 1
            break
    if f: l = m
    else: r = m
print(l)

Submission status: Runtime Error

Solution code:
n=input()
for i in range(n):
    a[i]=input()
tmp_out=0
for i in range(1, n-2):
    b=[0,0,0]
    for ii in range(i):
        b[0] += a[ii]

    for j in range(i+1, n-1):
        for jj in range(i, j):
            b[1] += a[jj]
        for jj in range(j+1, n):
            b[2] += a[jj]

    tmp_out=max(tmp_out, min(b))

print tmp_out

Submission status: Runtime Error

Solution code:
while True:
    n=input()
    for i in range(n):
        a[i]=input()
    tmp_out=0
    for i in range(1, n-2):
        b=[0,0,0]
        for ii in range(i):
            b[0] += a[ii]

        for j in range(i+1, n-1):
            for jj in range(i, j):
                b[1] += a[jj]
            for jj in range(j+1, n):
                b[2] += a[jj]

        tmp_out=max(tmp_out, min(b))

    print tmp_out

Submission status: Runtime Error

Solution code:
while True:
    n=input()
    a=[]
    for i in range(n):
        a[i]=input()
    tmp_out=0
    for i in range(1, n-2):
        b=[0,0,0]
        for ii in range(i):
            b[0] += a[ii]

        for j in range(i+1, n-1):
            for jj in range(i, j):
                b[1] += a[jj]
            for jj in range(j+1, n):
                b[2] += a[jj]

        tmp_out=max(tmp_out, min(b))

    print tmp_out

Submission status: Runtime Error

Solution code:
while True:
    n=input()
    a=[]
    for i in range(n):
        a.append(input())
    tmp_out=0
    for i in range(1, n-2):
        b=[0,0,0]
        for ii in range(i):
            b[0] += a[ii]

        for j in range(i+1, n-1):
            for jj in range(i, j):
                b[1] += a[jj]
            for jj in range(j+1, n):
                b[2] += a[jj]

        tmp_out=max(tmp_out, min(b))

    print tmp_out

Submission status: Runtime Error

Solution code:
n=input()
a=[]
for i in range(n):
    a.append(input())
tmp_out=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            b=[0,0,0]
            for ai in range(i,j):
                b[0]+=a[ai]
            for ai in range(j,k):
                b[1]+=a[ai]
            for ai in range(k,n):
                b[2]+=a[ai]
            for ai in range(0,i):
                b[2]+=a[ai]
            tmp_out=max(tmp_out, min(b))
    
print tmp_out

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

#ラジアンを度に変換
def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
#f = open("input2.txt")
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
#A_1&#12316;A_Nまでインデックス付きで格納
data = {i+1:0 for i in range(N)}
#i=1&#12316;i=Nの極座標を保持
polar = {i+1:0+0j for i in range(N)}
SUM = 0
for i in range(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in range(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	SUM_t += data[i]

min_arg = 0
#pをiに固定して考える
for i in range(1,N-1):
	p = polar[i]
	theta1 = rad_deg(c.phase(p))
	for j in range(i+1,N):
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		for k in range(j+1,N+1):
			r = polar[k]
			theta3 = rad_deg(c.phase(r))
			a = theta2 - theta1
			b = theta3 - theta2
			#print "%f,%f,%f" % (a,b,360-a-b)
			min_arg = max(min_arg, min(a,b,360-a-b))
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in range(N)}
polar = {i+1:0+0j for i in range(N)}
SUM = 0
for i in range(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in range(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	SUM_t += data[i]

min_arg = 0
for i in range(1,N-1):
	p = polar[i]
	theta1 = rad_deg(c.phase(p))
	#高速化?
	if(360-theta1 < min_arg):
		break
	print i
	for j in xrange(i+1,N):
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		#高速化?
		if(360-theta2 < min_arg):
			break
		###必要ないかも
		#if(a > MAX_deg):
		for k in xrange(j+1,N+1):
			r = polar[k]
			theta3 = rad_deg(c.phase(r))
			b = theta3 - theta2
			d = 360-a-b
			#高速化?
			###3つ目の条件いらないかも
			###dはmin_argより大きいので，
			if(a < min_arg or d < MAX_deg or min_arg == d or (a < theta1 and a < b)):
				break
			min_arg = max(min_arg, min(a,b,d))
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in range(N)}
polar = {i+1:0+0j for i in range(N)}
SUM = 0
for i in range(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in range(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	SUM_t += data[i]

min_arg = 0
for i in range(1,N-1):
	p = polar[i]
	theta1 = rad_deg(c.phase(p))
	#高速化?
	if(360-theta1 < min_arg):
		break
	for j in xrange(i+1,N):
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		#高速化?
		if(360-theta2 < min_arg):
			break
		###必要ないかも
		#if(a > MAX_deg):
		for k in xrange(j+1,N+1):
			r = polar[k]
			theta3 = rad_deg(c.phase(r))
			b = theta3 - theta2
			d = 360-a-b
			#高速化?
			###3つ目の条件いらないかも
			###dはmin_argより大きいので，
			if(a < min_arg or d < MAX_deg or min_arg == d or (a < theta1 and a < b)):
				break
			min_arg = max(min_arg, min(a,b,d))
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in range(N)}
polar = {i+1:0+0j for i in range(N)}
SUM = 0
for i in xrange(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in xrange(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	SUM_t += data[i]

min_arg = 0
for i in xrange(1,N-1):
	p = polar[i]
	theta1 = rad_deg(c.phase(p))
	#高速化?
	if(360-theta1 < min_arg):
		break
	for j in xrange(i+1,N):
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		#高速化?
		if(360-theta2 < min_arg):
			break
		###必要ないかも
		#if(a > MAX_deg):
		for k in xrange(j+1,N+1):
			r = polar[k]
			theta3 = rad_deg(c.phase(r))
			b = theta3 - theta2
			d = 360-a-b
			#高速化?
			###3つ目の条件いらないかも
			###dはmin_argより大きいので，
			if(a < min_arg or min_arg == d or (a < theta1 and a < b)):
				break
			min_arg = max(min_arg, min(a,b,d))
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in range(N)}
polar = {i+1:0+0j for i in range(N)}
SUM = 0
for i in xrange(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in xrange(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	SUM_t += data[i]

#適当なmin_argを与える---------------------------------------------------
min_arg = 0
p = polar[1]
theta1 = 0
for i in range(2,N):
	q = polar[i]
	if rad_deg(c.phase(q)) >= 120:
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		tmp = i
		break
for k in range(tmp,N+1):
	r = polar[k]
	theta3 = rad_deg(c.phase(r))
	b = theta3 - theta2
	d = 360-a-b
	#高速化?
	###3つ目の条件いらないかも
	min_arg = max(min_arg, min(a,b,d))
	if(d < b):
		break
#-----------------------------------------------------------------------

#初期位置の保存----------------------------------------------------------
judge1 = 0
judge2 = 0
p = polar[1]
theta1 = 0
for j in range(2,N):
	if judge1 == 0:
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		if a >= min_arg:
			tmp1 = j
			break
for k in xrange(tmp+1,N+1):
	if judge2 == 0:
		r = polar[k]
		theta3 = rad_deg(c.phase(r))
		b = theta3 - theta2
		if b >= min_arg :
			tmp2 = k
			d = 360-a-b
			break
#-----------------------------------------------------------------------

#ループ処理--------------------------------------------------------------
judge = 0
#pをiに固定
for i in range(1,N-1):
	p = polar[i]
	theta1 = rad_deg(c.phase(p))
	#tmp1の更新
	if i > 1:
		while theta2 - theta1 < min_arg and tmp1 <= N-2:
			tmp1 += 1
			q = polar[tmp1]
			theta2 = rad_deg(c.phase(q))
			judge = 1
	#高速化?
	if(360-theta1 < min_arg):
		break
	for j in range(tmp1,N):
		q = polar[j]
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		#tmp1の更新
		if judge == 1:
			while theta3 - theta2 < min_arg and tmp2 <= N-1:
				tmp2 += 1
				r = polar[tmp2]
				theta3 = rad_deg(c.phase(r))
		#高速化?
		if(360-theta2 < min_arg):
			break
		for k in range(tmp2,N+1):
			r = polar[k]
			theta3 = rad_deg(c.phase(r))
			b = theta3 - theta2
			d = 360-a-b
			#高速化?
			###3つ目の条件いらないかも
			min_arg = max(min_arg, min(a,b,d))
			if(d < b or (a < theta1 and a < b)):
				break
#-----------------------------------------------------------------------
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in range(N)}
polar = {i+1:0+0j for i in range(N)}
SUM = 0
sumlist = []
for i in xrange(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in xrange(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	sumlist.append(rad_deg(c.phase(polar[i])))
	SUM_t += data[i]
sumlist.append(360.0)

min_arg = 0
p = polar[1]
theta1 = 0
for i in range(2,N):
	q = polar[i]
	if rad_deg(c.phase(q)) >= 120:
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		tmp = i
		break
for k in range(tmp,N+1):
	r = polar[k]
	theta3 = rad_deg(c.phase(r))
	b = theta3 - theta2
	d = 360-a-b
	min_arg = max(min_arg, min(a,b,d))
	if(d < b):
		break

tmp0 = 0
tmp1 = 1
tmp2 = 2
p = sumlist[tmp1] -sumlist[tmp0]
q = sumlist[tmp2] - sumlist[tmp1]
r = 360.0 - sumlist[tmp2] +sumlist[tmp0]
min_arg = max(min_arg, min(p,q,r))
length = len(sumlist)

while(tmp0 < round(N/2.0) and tmp2 < length -1  and tmp1 < tmp2):
	tmp1 = tmp0 + 1
	tmp2 = tmp1 + 1
	p = sumlist[tmp1] - sumlist[tmp0]
	q = sumlist[tmp2]-sumlist[tmp1]
	r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
	while(r >= min_arg and tmp2 < length -2):
		if(sumlist[tmp2]-sumlist[tmp1] < min_arg):
			tmp2 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
		elif(sumlist[tmp1] - sumlist[tmp0] < min_arg):
			tmp1 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
		else:
			tmp2 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
	tmp0 += 1
	
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math as m
import cmath as c
import numbers

def rad_deg(rad):
	if rad >= 0:
		return m.degrees(rad)
	else:
		return m.degrees(2*pi-abs(rad))

input_lines = []
input_lines.append(raw_input())
N = int(input_lines[0])
pi = c.pi
data = {i+1:0 for i in xrange(N)}
polar = {i+1:0+0j for i in xrange(N)}
SUM = 0
sumlist = []
for i in xrange(1,N+1):
	input_lines.append(raw_input())
	data[i] = int(input_lines[i])
	SUM += int(input_lines[i])
SUM_t = 0.0
for i in xrange(1,N+1):
	polar[i] = c.exp(1j*SUM_t/SUM*2*pi)
	sumlist.append(rad_deg(c.phase(polar[i])))
	SUM_t += data[i]
sumlist.append(360.0)

min_arg = 0
p = polar[1]
theta1 = 0
for i in xrange(2,N):
	q = polar[i]
	if rad_deg(c.phase(q)) >= 120:
		theta2 = rad_deg(c.phase(q))
		a = theta2 - theta1
		tmp = i
		break
for k in xrange(tmp,N+1):
	r = polar[k]
	theta3 = rad_deg(c.phase(r))
	b = theta3 - theta2
	d = 360-a-b
	min_arg = max(min_arg, min(a,b,d))
	if(d < b):
		break

tmp0 = 0
tmp1 = 1
tmp2 = 2
p = sumlist[tmp1] -sumlist[tmp0]
q = sumlist[tmp2] - sumlist[tmp1]
r = 360.0 - sumlist[tmp2] +sumlist[tmp0]
min_arg = max(min_arg, min(p,q,r))
length = len(sumlist)

while(tmp0 < round(N/2.0) and tmp2 < length -1  and tmp1 < tmp2):
	tmp1 = tmp0 + 1
	tmp2 = tmp1 + 1
	p = sumlist[tmp1] - sumlist[tmp0]
	q = sumlist[tmp2]-sumlist[tmp1]
	r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
	while(r >= min_arg and tmp2 < length -2):
		if(sumlist[tmp2]-sumlist[tmp1] < min_arg):
			tmp2 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
		elif(sumlist[tmp1] - sumlist[tmp0] < min_arg):
			tmp1 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
		else:
			tmp2 += 1
			p = sumlist[tmp1] - sumlist[tmp0]
			q = sumlist[tmp2]-sumlist[tmp1]
			r = 360.0 - sumlist[tmp2] + sumlist[tmp0]
			min_arg = max(min_arg, min(p,q,r))
	tmp0 += 1
	
			
print int(round((min_arg/360)*SUM))

Submission status: Runtime Error

Solution code:
import sys
import bisect

f = sys.stdin

#n = int(f.readline())
a = list(map(int,f))
a[0] = 0
for i in range(1,len(a)):
    a[i] += a[i - 1]

sum_a = a[-1]
third = sum_a // 3

ret = []

for i in range(bisect.bisect_left(a, third)):
    nick1 = bisect.bisect_left(a, a[i] + third,lo=i)
    
    for ni1 in (nick1-1,nick1):
        second = min(third,(sum_a - (a[ni1] - a[i])) // 2)
        nick2 = bisect.bisect_left(a, a[ni1] + second,lo=nick)
        for ni2 in (nick2-1,nick2):
            if len(a) <= ni2:
                continue
            piece1 = a[ni1] - a[i]
            piece2 = a[ni2] - a[ni1]
            piece3 = sum_a - piece1 - piece2
            ret.append(min(piece1,piece2,piece3))
print(max(ret))

Submission status: Runtime Error

Solution code:
def checksmallest(edi,Clist,partS):
    #rotate Alist so that sti is 0
    Blist=Clist[edi:]
    m=len(Blist)
    BS=sum(Blist)
    head=0
    tail=m
    body=m/2
    while(head!=body and tail!=body):
        left=sum(Blist[0:body])
        right=sum(Blist[body:m])
        #print partS,left,right
        if min(right,left)>=partS:
            return True
        else:
            if left>=right:
                tail=body
                body=(head+tail)/2
            else:
                head=body
                body=(head+tail)/2
    return False


N=int(raw_input())
Alist=[]
for i in range(N):
    Alist.append(int(raw_input()))
Asum=sum(Alist)

smallest=0

for sti in range(N):
    #rotate so that sti=0
    Clist=Alist[sti:]+Alist[:sti]
    for edi in range(1,N+1):
        partS=sum(Clist[:edi])
        if smallest<partS and partS<=Asum/3:
            #print sti,edi,partS
            if checksmallest(edi,Clist,partS):
                smallest=partS
                
print smallest

Submission status: Runtime Error

Solution code:
def checksmallest(edi,Clist,partS):
    #rotate Alist so that sti is 0
    Blist=Clist[edi:]
    m=len(Blist)
    BS=sum(Blist)
    head=0
    tail=m
    body=m/2
    while(head!=body and tail!=body):
        left=sum(Blist[0:body])
        right=sum(Blist[body:m])
        #print partS,left,right
        if min(right,left)>=partS:
            return True
        else:
            if left>=right:
                tail=body
                body=(head+tail)/2
            else:
                head=body
                body=(head+tail)/2
    return False


N=int(raw_input())
Alist=[]
for i in range(N):
    Alist.append(int(raw_input()))
Asum=sum(Alist)

smallest=0

for sti in range(N):
    #rotate so that sti=0
    Clist=Alist[sti:]+Alist[:sti]
    for edi in range(1,N+1):
        partS=sum(Clist[:edi])
        if partS>Asum/3:
            break
        elif smallest<partS and partS<=Asum/3:
            #print sti,edi,partS
            if checksmallest(edi,Clist,partS):
                smallest=partS
                
print smallest

Submission status: Runtime Error

Solution code:
def checksmallest(edi,Clist,partS):
    #rotate Alist so that sti is 0
    Blist=Clist[edi:]
    m=len(Blist)
    BS=sum(Blist)
    head=0
    tail=m
    body=m/2
    while(head!=body and tail!=body):
        left=sum(Blist[0:body])
        right=sum(Blist[body:m])
        #print partS,left,right
        if min(right,left)>=partS:
            return True
        else:
            if left>=right:
                tail=body
                body=(head+tail)/2
            else:
                head=body
                body=(head+tail)/2
    return False


N=int(raw_input())
Alist=[]
for i in range(N):
    Alist.append(int(raw_input()))
Asum=sum(Alist)

smallest=0

for sti in range(N):
    #rotate so that sti=0
    Clist=Alist[sti:]+Alist[:sti]
    partS=sum(Clist)
    edk=N-1
    while(partS>Asum/3):
        partS-=Clist[edk]
        edk-=1
    for edi in range(edk+1,1,-1):
        partS=sum(Clist[:edi])
        #print sti,edi,partS
        if smallest<partS and partS<=Asum/3:
            if checksmallest(edi,Clist,partS):
                smallest=partS
                
print smallest

Submission status: Runtime Error

Solution code:
def checksmallest(edi,Clist,partS):
    #rotate Alist so that sti is 0
    Blist=Clist[edi:]
    m=len(Blist)
    BS=sum(Blist)
    head=0
    tail=m
    body=m/2
    while(head!=body and tail!=body):
        left=sum(Blist[0:body])
        right=sum(Blist[body:m])
        #print partS,left,right
        if min(right,left)>=partS:
            return True
        else:
            if left>=right:
                tail=body
                body=(head+tail)/2
            else:
                head=body
                body=(head+tail)/2
    return False


N=int(raw_input())
Alist=[]
for i in range(N):
    Alist.append(int(raw_input()))
Asum=sum(Alist)

smallest=0

edk_before=1

for sti in range(N):
    #rotate so that sti=0
    Clist=Alist[sti:]+Alist[:sti]
    edk=edk_before-1
    partS=sum(Clist[:edk])
    while(partS<Asum/3):
        partS+=Clist[edk]
        edk+=1
    edk_before=edk
    for edi in range(edk+1,1,-1):
        partS=sum(Clist[:edi])
        #print sti,edi,partS
        if smallest<partS and partS<=Asum/3:
            if checksmallest(edi,Clist,partS):
                smallest=partS
        elif smallest>partS:
            break
print smallest

Submission status: Runtime Error

Solution code:
__Author__ = 'Anomino'
# coding:UTF-8
import numpy as np

def AskUser() : 
		number = int(raw_input())
		baum = []

		for value in range(number) : 
			baum.append(int(raw_input()))

		return baum

def CutBaum(baum, cuts) :
		ideal = sum(baum) / cuts
		piece_of_baum = []
		tmp_baum = 0

		for value in range(len(baum)) : 
				if len(baum) == (cuts - 1) : 
						piece_of_baum.append(sum(baum[value :]))
						break

				if np.abs(ideal - tmp_baum) > np.abs(ideal - tmp_baum - baum[value]) : 
						tmp_baum = tmp_baum + baum[value]
				else : 
						piece_of_baum.append(tmp_baum)
						tmp_baum = baum[value]
		return min(piece_of_baum)

if __name__ == '__main__' : 
		baum = AskUser()
		min_baum = CutBaum(baum, 3)

		print min_baum

Submission status: Runtime Error

Solution code:
n = int(input())
a = [0]*n
for i in range(n):
    a[i] = int(input())

m = 0
opt = [0,0,0]
count = 0
for i in range(n-1):
    for j in range(i+1,n):
        for k in range(j+1,n):
            g1,g2,g3 = 0,0,0
            #print(i,j,k)
            if i != 0:
                for x in range(i+1,j):
                    g1 += a[x]
            else:
                for x in range(i,j):
                    g1 += a[x]
            for x in range(j,k):
                g2 += a[x]
            if i == 0:
                for x in range(k,n):
                    g3 += a[x]
            elif k == n:
                for x in range(i+1):
                    g3 += a[x]
            else:
                for x in range(k,n):
                    g3 += a[x]
                for x in range(i+1):
                    g3 += a[x]
            count +=1
            l = min(g1,g2,g3)
            if m < l:
                m = l
                opt = [i,j,k]

print(m)

Submission status: Runtime Error

Solution code:
from itertools import combinations

def min(a,b,c):
    if a<=b and a<=c:
        return a
    elif b<=c:
        return b
    else:
        return c

N=int(input())
list=[int(input())]
for i in range(1,N):
    list.append(int(input())+list[-1])


a=combinations(range(0,N),3)

max_of_minimumsize=0

for i in a:
    cut1=i[0]
    cut2=i[1]
    cut3=i[2]

    piece1=list[cut1]+list[-1]-list[cut3]
    piece2=list[cut2]-list[cut1]
    piece3=list[cut3]-list[cut2]
    minpiece=min(piece1,piece2,piece3)

    if max_of_minimumsize<=minpiece:
        max_of_minimumsize=minpiece

print(max_of_minimumsize)

Submission status: Runtime Error

Solution code:
def min(a,b,c):
    if a<=b and a<=c:
        return a
    elif b<=c:
        return b
    else:
        return c

N=int(input())
list=[int(input())]
for i in range(1,N):
    list.append(int(input())+list[-1])




max_of_minimumsize=0

for cut1 in range(N-2):
    for cut2 in range(cut1,N-1):
        for cut3 in range(cut2,N):

            piece1=list[cut1]+list[-1]-list[cut3]
            piece2=list[cut2]-list[cut1]
            piece3=list[cut3]-list[cut2]
            minpiece=min(piece1,piece2,piece3)

            if max_of_minimumsize<=minpiece:
                max_of_minimumsize=minpiece

print(max_of_minimumsize)

Submission status: Runtime Error

Solution code:
# coding: utf-8

numberOfLines = int(input())
cuttingPoints = [0 for _ in range(numberOfLines)]
for readLine in range(numberOfLines):
    cuttingPoints[readLine] = int(input())

def selectMaxDifference(sumOfFirst, sumOfSecond, sumOfThird):
    differenceBetween1And2 = abs(sumOfFirst - sumOfSecond)
    differenceBetween1And3 = abs(sumOfFirst - sumOfThird)
    differenceBetween2And3 = abs(sumOfSecond - sumOfThird)
    return max([differenceBetween1And2, differenceBetween1And3, differenceBetween2And3])

def calculateSum(data, start, first, second, third, last):
    sumOfFirst = sum(data[start:start+first])
    sumOfSecond = sum(data[start+first:start+first+second])
    headFirst = 0
    tailFirst = 0
    headThird = 0
    # ??¬??\?????????????????????????????????
    lastValue = start + first + second + third - len(data)
    if lastValue < 0:
        thirdLength = third
        headFirst = start
        tailFirst = abs(lastValue)
    else:
        thirdLength = start + first + second + third
        headFirst = start - lastValue
        headThird = lastValue
        if lastValue == 0:
            headFirst = len(data) - (first + second + third)
        #if start == 2 and first == 14 and second == 7 and third == 8:        
        #    print("hf={0} tf={1} ht={2}".format(headFirst, tailFirst, headThird))
    sumOfThird = sum(data[start+first+second:start+first+second+thirdLength])
    if headFirst > 0:
        sumOfFirst += sum(data[0+headThird:headThird+headFirst])
    if tailFirst > 0:
        sumOfFirst += sum(data[start+first+second+third:start+first+second+third+tailFirst])
    if headThird > 0:
        sumOfThird += sum(data[0:headThird])
    return sumOfFirst, sumOfSecond, sumOfThird

minDifference = 100000
minPiece = 0
for start in range(0, numberOfLines - 2):
    for first in range(1, numberOfLines - 1):
        for second in range(1, numberOfLines - 1):
            if start + first + second > numberOfLines - 1:
                continue
            for third in range(1, numberOfLines - 1):
                if first + second + third > numberOfLines:
                    break
                last = numberOfLines - (first + second + third)
                sumOfNo1, sumOfNo2, sumOfNo3 = calculateSum(cuttingPoints, start, first, second, third, last)
                difference = selectMaxDifference(sumOfNo1, sumOfNo2, sumOfNo3)
                if difference < minDifference:
                    minDifference = difference
                    minPiece = min([sumOfNo1, sumOfNo2, sumOfNo3])
                    #print("{0} + ({1}, {2}, {3}) = [{4} {5} {6}] => {7} diff={8}".format(start, first, second, third, sumOfNo1, sumOfNo2, sumOfNo3, minPiece, difference))
print(minPiece)

Submission status: Runtime Error

Solution code:
#??\???
N = input()
A = [int(input()) for i in range(N)]

s = sum(A)#?????????????????????????????????
min_max = 0

for i in range(1,N+1):
	for j in range(i+1,N+1):
		for k in range(k+1,N+1):
			m=min(sum(A[1:i]),sum(A[i+1:j]),sum(A)-N)
			if(m>min_max):
				min_max=m
print(min_max)