Problem:


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

完全平等二国間貿易

サイバースペースにあるアイヅ国はワカマツ国と情報貿易を行っています。２つの国はお互いに有用なデータを交換することで経済発展を遂げています。博愛と平等、そして何よりも会津地方の古い言葉である、「ならぬことはならぬものです」を国是とする両国は、定期的に貿易状況の調査を行っています。

調査では、バイト単位でアイヅ国から見たデータ流入量から流出量を引いた値を、１ナノ秒ごとに求めた表が与えられます。その表から、値の総和が０になる最長の区間を見つけます。この区間が長いほど、平等性が保たれていると判断します。

貿易状況が記録された表が与えられたとき、値の総和が０になる最長の区間の長さを求めるプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N
d1
d2
:
dN

１行目に、表に書かれた値の数 N (1 ≤ N ≤ 200000) が与えられる。続く N 行に、表の i 行目に書かれた値を示す整数 di (-109 ≤ di ≤ 109) が与えられる。

Output

表から得られる、総和が０になる最長の区間の長さを１行に出力する。そのような区間が存在しない場合、「0」を１行に出力する。

Sample Input 1

5
18
102
-155
53
32

Sample Output 1

3

入力例１では、２行目から４行目までの値の総和が０になるので、最長の区間の長さが3になる。

Sample Input 2

4
1
1
-1
-1

Sample Output 2

4

入力例２では、２行目から３行目の総和が０になるが、１行目から４行目までの値の総和も０になるので、最長の区間の長さが4になる。



Sample input:
5
18
102
-155
53
32


Sample output:
3

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
sum = int(0)
maxv = -1 << 30
dict = {sum : int(-1)}

for i in range(N):
    val = int(raw_input())
    sum += val
    
    if dict.get(sum, int(-2)) != -2 :
        maxv = max(maxv, i - dict[sum])
    else :
        dict[sum] = i

if maxv == -1 << 30 :
    print 'NA'
else : 
    print maxv

Submission status: Wrong Answer

Solution code:
n = int(input())
d = []
a = 0
for _ in range(n):d.append(int(input()))
v = [[-1] * n for _ in range(n)]
v[0][0] = 0
for i in range(n):
    v[0][- i - 1] = v[0][- i] + d[i]
for i in range(1, n):
    for j in range(n - i):
        v[i][j + i] = v[i - 1][j] - d[i - 1]
a = 0
for i in range(n):
    try:a = max(a,n -v[i].index(0))
    except:pass
print(a)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = []
a = 0
for _ in range(n):d.append(int(input()))
v = [[-1] * n for _ in range(n)]
v[0][0] = 0
for i in range(n):
    v[0][- i - 1] = v[0][- i] + d[i]
for i in range(1, n):
    for j in range(n - i):
        v[i][j] = v[i - 1][j] - d[i - 1]
a = 0
print(v)
for i in range(n):
    try:a = max(a,n -v[i].index(0) - i)
    except:pass
print(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
d = [int(input()) for _ in range(n)]
b = [sum(d)]
for i in range(n):
    if 0 in b:
        print(n - i)
        break
    c = b[-1]
    b = [b[j] - d[-i + j  -1] for j in range(i + 1)]
    b.append(c - d[i])
else:print(0)

Submission status: Memory Limit Exceeded

Solution code:
n = int(input())
d = []
a = 0
for _ in range(n):d.append(int(input()))
v = [[-1] * n for _ in range(n)]
v[0][0] = 0
for i in range(n):
    v[0][- i - 1] = v[0][- i] + d[i]
for i in range(1, n):
    for j in range(n - i):
        v[i][j] = v[i - 1][j] - d[i - 1]
a = 0
for i in range(n):
    try:a = max(a,n -v[i].index(0) - i)
    except:pass
print(a)

Submission status: Accepted

Solution code:
N = int(raw_input())
sum = int(0)
maxv = 0
dict = {sum : int(-1)}

for i in range(N):
    val = int(raw_input())
    sum += val
    
    if dict.get(sum, int(-2)) != -2 :
        maxv = max(maxv, i - dict[sum])
    else :
        dict[sum] = i

print maxv

Submission status: Accepted

Solution code:
n = int(input())
D = [int(input()) for i in range(n)]
S = {}

s = ans = 0
S[0] = -1
for i in range(n):
    s += D[i]
    if s in S:
        ans = max(i - S[s], ans)
    else:
        S[s] = i
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

dic = defaultdict(list)
keys = set()
n = int(input())
acc = 0
dic[0].append(0)
keys.add(0)
for i in range(1, n + 1):
  d = int(input())
  acc += d
  dic[acc].append(i)
  keys.add(acc)

ans = 0
for key in keys:
  lst = dic[key]
  ans = max(ans, max(lst) - min(lst))

print(ans)