Problem:


Square Route

スクウェア・ルート

English text is not available in this practice contest.

このたび新しい豪邸を建てることを決めた大富豪の品田氏は，どの街に新邸を建てようかと悩んでいる．実は，品田氏は正方形がとても好きという変わった人物であり，そのため少しでも正方形の多い街に住みたいと思っている．

品田氏は，碁盤目状に道路の整備された街の一覧を手に入れて，それぞれの街について，道路により形作られる正方形の個数を数えることにした．ところが，道と道の間隔は一定とは限らないため，手作業で正方形を数えるのは大変である．そこであなたには，碁盤目状の道路の情報が与えられたときに，正方形の個数を数えるプログラムを書いて欲しい．

Input

入力は複数のデータセットから構成されており，各データセットは以下のような構成になっている．

N M

h1

h2

...

hN

w1

w2

...

wM

1 行目には 2 つの正の整数 N, M (1 ≦ N, M ≦ 1500) が与えられる．続く N 行 h1, h2, ..., hN (1 ≦ hi ≦ 1000）は，道路と道路の南北方向の間隔を表す．ここで hi は北から i 番目の道路と北から i + 1 番目の道路の間隔である．同様に，続く M 行 w1, ..., wM (1 ≦ wi ≦ 1000）は，道路と道路の東西方向の間隔を表す．ここで wi は西から i 番目の道路と西から i + 1 番目の道路の間隔である．道路自体の幅は十分細いため考慮する必要はない．

図 D-1: 最初のデータセット

N = M = 0 は入力の終端を示しており，データセットには含めない．

Output

各データセットに対して，正方形の個数を 1 行に出力しなさい．たとえば，Sample Input の最初のデータセットにおいては，以下のとおり 6 個の正方形を含むので，このデータセットに対する出力は 6 となる．

図 D-2: 最初のデータセットに含まれる正方形

Sample Input

3 3
1
1
4
2
3
1
1 2
10
10
10
0 0

Output for the Sample Input

6
2



Sample input:
3 3
1
1
4
2
3
1
1 2
10
10
10
0 0


Sample output:
6
2

Submission status: Accepted

Solution code:
from collections import defaultdict

while 1:
    ws, hs, w, h = defaultdict(int), defaultdict(int), [], []
    n, m = map(int, raw_input().split())
    if n|m == 0: break

    for i in range(n):
        t = s = input()
        ws[s]+=1
        for pw in reversed(w):
            s+=pw
            ws[s]+=1
        w.append(t)

    for i in range(m):
        t = s = input()
        hs[s]+=1
        for pw in reversed(h):
            s+=pw
            hs[s]+=1
        h.append(t)

    print sum(ws[a] * hs[a] for a in ws if a in hs)

Submission status: Accepted

Solution code:
#演習2-16
from bisect import bisect_left, bisect_right #二分探索
from collections import Counter 

def how_many(a, x):
    # リストaのなかでxが何個あるのかを返す関数
    return bisect_right(a, x) - bisect_left(a, x)


def solve(n, m):
    # とく関数
    a = [int(input()) for _ in range(n)]
    b = [int(input()) for _ in range(m)]

    sum_a = [0 for i in range(n + 1)]
    sum_b = [0 for i in range(m + 1)]

    # sum_a[i]=縦の始点からの距離
    # sum_b[i]=横の始点からの距離

    for i in range(n):
        sum_a[i + 1] = sum_a[i] + a[i]

    for i in range(m):
        sum_b[i + 1] = sum_b[i] + b[i]

    all_range_h = []

    all_range_w = []

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            all_range_h.append(sum_a[j] - sum_a[i])

    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            all_range_w.append(sum_b[j] - sum_b[i])

        # all_range_h=縦の長さでの、ありうる長さの組み合わせ
        # all_range_w=横の長さでの、ありうる長さの組み合わせ

    all_range_w.sort()
    # 縦の長さを決めて、（Lとする）そのとり方がX通りあったとする。この時、横の長さがLとなるものが何個あるのかを考える。これを考える際に二部探索するので予め縦の長さの組み合わせをソートしておく。
    # これをYとしたときX*Yがこの時のありうる総数である。

    ans = 0

    data_h = dict(Counter(all_range_h))

    # data_hに（key=ありうる縦の長さの個数、value=その取り方の総数)を持つ辞書を作る。

    for key in data_h.keys():
        ans += data_h[key] * how_many(all_range_w, key)

    return ans


flag = True

while flag:
    n, m = map(int, input().split())
    # 終わりのサイン:(n,m)=(0,0)
    if n == m == 0:
        flag = False
        break
    else:
        print(solve(n, m))

Submission status: Accepted

Solution code:
while True:
    n,m= map(int,input().split())
    if n==0:
        break
    count_h,count_w,count= 0,0,0
    h,w= [0],[0]
    for i in range(0,n):
        count_h+= int(input())
        h.append(count_h)
    for i in range(0,m):
        count_w+= int(input())
        w.append(count_w)

    pos=[0]*1500010
    ans=0
    for i in range(0,n):
        for j in range(i+1,n+1):
            pos[h[j]- h[i]]+= 1
    for i in range(0,m):
        for j in range(i+1,m+1):
            ans= ans+ pos[w[j]-w[i]]
    print(ans)

Submission status: Accepted

Solution code:
def solve(n, m):
    h = [0]
    for i in range(n):
        h.append(int(input()) + h[-1])
    w = [0]
    for j in range(m):
        w.append(int(input()) + w[-1])
    D = {}
    for i in range(n + 1):
        for j in range(m + 1):
            s = h[i] + w[j]
            if s in D:
                D[s] += 1
            else:
                D[s] = 1
    ans = 0
    for key, value in D.items():
        ans += value * (value - 1) / 2
    return print(int(ans))
while True:
    n, m = map(int,input().split())
    if (n, m) == (0, 0):
        break
    solve(n,m)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def solve(n,m):
    H = [int(input()) for _ in range(n)]
    W = [int(input()) for _ in range(m)]

    H_length = [0] * 1500000
    W_length = [0] * 1500000
    for i in range(n):
        height = 0
        for j in range(i,n):
            height += H[j]
            H_length[height] += 1
    
    for i in range(m):
        width = 0
        for j in range(i,m):
            width += W[j]
            W_length[width] += 1
    
    ans = sum(h*w for h,w in zip(H_length,W_length))
    print(ans)

def main():
    while True:
        n,m = map(int,input().split())
        if n == 0:
            return
        solve(n,m)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from bisect import bisect_left, bisect_right
from collections import Counter

# 主題　ICPC
# square route
# 使用言語:Python3
# URL:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2015&lang=jp


def how_many(a, x):
    # リストaのなかでxが何個あるのかを返す関数
    return bisect_right(a, x) - bisect_left(a, x)


def solve(n, m):
    # とく関数
    a = [int(input()) for _ in range(n)]
    b = [int(input()) for _ in range(m)]

    sum_a = [0 for i in range(n + 1)]
    sum_b = [0 for i in range(m + 1)]

    # sum_a[i]=縦の左からi番目までの累積和(i=0 の時は0と定義する)
    # sum_b[i]=横の左からi番目までの累積和(i=0　の時は0と定義する)

    for i in range(n):
        sum_a[i + 1] = sum_a[i] + a[i]

    for i in range(m):
        sum_b[i + 1] = sum_b[i] + b[i]

    all_range_h = []

    all_range_w = []

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            all_range_h.append(sum_a[j] - sum_a[i])

    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            all_range_w.append(sum_b[j] - sum_b[i])

        # all_range_h=縦の長さでの、ありうる長さの組み合わせ（重複あり） =nC2
        # all_range_w=横の長さでの、ありうる長さの組み合わせ（重複あり） =mC2

    all_range_w.sort()
    # 縦の長さを決めて、（Lとする）そのとり方がX通りあったとする。この時、横の長さがLとなるものが何個あるのかを考える。これを考える際に二部探索するので予め縦の長さの組み合わせをソートしておく。
    # これをYとしたときX*Yがこの時のありうる総数である。

    ans = 0

    data_h = dict(Counter(all_range_h))

    # data_hに（key=ありうる縦の長さの個数、value=その取り方の総数)を持つ辞書を作る。

    for key in data_h.keys():
        ans += data_h[key] * how_many(all_range_w, key)

    return ans


flag = True

while flag:
    n, m = map(int, input().split())
    # 終わりのサイン:(n,m)=(0,0)
    if n == m == 0:
        flag = False
        break
    else:
        print(solve(n, m))

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    from itertools import accumulate
    from collections import Counter
    
    def combin(n):
        return n * (n - 1) // 2
    
    f_i = stdin
    
    while True:
        N, M = map(int, f_i.readline().split())
        if N == 0:
            break
        
        Y = (0,) + tuple(accumulate(int(f_i.readline()) for i in range(N)))
        X = (0,) + tuple(accumulate(int(f_i.readline()) for i in range(M)))
        
        V = Counter(y - x for x in X for y in Y)
        
        print(sum(map(combin, V.values())))
solve()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


while True:
    N,M = inpl()
    if N == 0:
        break
    hh = [inp() for _ in range(N)]
    ww = [inp() for _ in range(M)]
    cnts = defaultdict(int)


    rhh = hh[:]
    for i in range(1,N):
        rhh[i] += rhh[i-1]
    rhh.append(0)

    for i in range(N+1):
        for j in range(i+1,N+1):
            tmp = rhh[j-1] - rhh[i-1]
            cnts[tmp] += 1

    rww = ww[:]
    for i in range(1,M):
        rww[i] += rww[i-1]
    rww.append(0)

    ans = 0
    for i in range(M+1):
        for j in range(i+1,M+1):
            tmp = rww[j-1] - rww[i-1]
            ans += cnts[tmp]

    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate, product

while True:
    n, m = map(int, input().split())
    if n == 0:
        exit()
    h = [int(input()) for _ in range(n)]
    w = [int(input()) for _ in range(m)]

    hs = [0] + list(accumulate(h))
    ws = [0] + list(accumulate(w))

    dic = {}
    for l, r in product(range(m + 1), range(m + 1)):
        if l >= r:
            continue
        dw = ws[r] - ws[l]
        dic[dw] = dic[dw] + 1 if dw in dic else 1

    ans = 0
    for l, r in product(range(n + 1), range(n + 1)):
        if l >= r:
            continue
        dh = hs[r] - hs[l]
        if dh in dic:
            ans += dic[dh]

    print(ans)

Submission status: Accepted

Solution code:
#復習用
import bisect

while 1:
    n,m = map(int, input().split())
    if n == m == 0:
        break
    h = [0] + [int(input()) for i in range(n)]
    w = [0] + [int(input()) for j in range(m)]
    for i in range(n):
        h[i+1] += h[i]
    for i in range(m):
        w[i+1] += w[i]
    a = [0 for i in range(n*(n+1)//2)]#行の道幅すべてを入れるリスト
    b = [0 for i in range(m*(m+1)//2)]#列の道幅すべてを入れるリスト
    k = 0
    for i in range(1,n+1):
        for j in range(i):
            a[k] = h[i]-h[j]
            k += 1

    k = 0
    for i in range(1,m+1):
        for j in range(i):
            b[k] = w[i]-w[j]
            k += 1

    ans = 0
    b.sort()
    #print(a)
    #print(b)
    for i in a:
        l = bisect.bisect_left(b,i)#1つ目の引数はソート済みのリスト 2つ目の引数は挿入する値 bisect_leftの返り値はソートを保った挿入箇所の一番左
        r = bisect.bisect_right(b,i)
        ans += r-l#行間隔と同じ列間隔の個数を足す(bが1,2,4でiが3のときlとrはともに2で0、iが2ならlは1,rは2で1)
    print(ans)

Submission status: Accepted

Solution code:
import bisect

while 1:
    n,m = map(int, input().split())
    if n == m == 0:
        break
    h = [int(input()) for i in range(n)]
    w = [int(input()) for j in range(m)]
    for i in range(n-1):
        h[i+1] += h[i]
    for i in range(m-1):
        w[i+1] += w[i]
    h.insert(0,0)
    w.insert(0,0)
    a = [0 for i in range(n*(n+1)//2)]
    b = [0 for i in range(m*(m+1)//2)]
    k = 0
    for i in range(1,n+1):
        for j in range(i):
            a[k] = h[i]-h[j]
            k += 1

    k = 0
    for i in range(1,m+1):
        for j in range(i):
            b[k] = w[i]-w[j]
            k += 1

    ans = 0
    b.sort()
    for i in a:
        l = bisect.bisect_left(b,i)
        r = bisect.bisect_right(b,i)
        ans += r-l
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def solve(n, m):
  H = [int(input()) for i in range(n)]
  W = [int(input()) for i in range(m)]

  D_h = defaultdict(int)
  D_w = defaultdict(int)

  cum_h = [0]
  cum_w = [0]

  for h in H:
    cum_h.append(cum_h[-1] + h)

  for w in W:
    cum_w.append(cum_w[-1] + w)

  for i in range(n + 1):
    for j in range(i + 1, n + 1):
      D_h[cum_h[j] - cum_h[i]] += 1

  for i in range(m + 1):
    for j in range(i + 1, m + 1):
      D_w[cum_w[j] - cum_w[i]] += 1

  ans = 0

  for k, v in D_h.items():
    ans += v * D_w[k]

  print(ans)
  
while True:
  n, m = [int(i) for i in input().split()]
  if (n, m) == (0, 0):
    break
  solve(n, m)

Submission status: Accepted

Solution code:
import collections

def accumulate(a):
	sum = 0
	result = [0]
	for x in a:
		sum += x
		result.append(sum)
	return result

def aggregate(a):
	result = []
	for j in range(len(a)):
		for i in range(j):
			result.append(a[j] - a[i])
	return result

while True:
	H, W = map(int, input().split())
	if H == 0: break

	h = [int(input()) for _ in range(H)]
	w = [int(input()) for _ in range(W)]

	ha = aggregate(accumulate(h))
	wa = aggregate(accumulate(w))

	ha.sort()
	wa.sort()
	hc = collections.Counter(ha)
	wc = collections.Counter(wa)

	count = 0
	for size in set(hc.keys()) & set(wc.keys()):
		count += hc[size] * wc[size]

	print(count)

Submission status: Accepted

Solution code:
while True:
    N, M = map(int,input().split())
    if M == 0:
        exit()

    h = [0]+[int(input()) for i in range(N)]
    N += 1
    for i in range(1,N):
        h[i] += h[i-1]
    w = [0]+[int(input()) for i in range(M)]
    M += 1
    for i in range(1,M):
        w[i] += w[i-1]

    h_pat = {}
    w_pat = {}
    for i in range(N-1):
        for j in range(i+1,N):
            height = h[j] - h[i]
            if height not in h_pat:
                h_pat[height] = 1
            else:
                h_pat[height] += 1
    for i in range(M-1):
        for j in range(i+1,M):
            width = w[j] - w[i]
            if width not in w_pat:
                w_pat[width] = 1
            else:
                w_pat[width] += 1

    ans = 0
    for k, v in h_pat.items():
        if k in w_pat:
            ans += w_pat[k] * v

    # print(h_pat)
    # print(w_pat)
    print(ans)

Submission status: Accepted

Solution code:
def solve():
    lH=[]
    for i in range(N):
        for j in range(i,N):
            lH += [sumH[j+1]-sumH[i]]
    lH = sorted(lH)
    lW=[]
    for i in range(M):
        for j in range(i,M):
            lW += [sumW[j+1]-sumW[i]]
    lW = sorted(lW)

    mul = {}
    dub = {}
    for i in lH:
        if i in mul.keys():
            mul[i] += 1
        else:
            mul[i] = 1
            dub[i] = 0
    for j in lW:
        if j in dub.keys():
            dub[j] += 1
    count = 0
    #print(mul,dub)
    for k in mul.keys():
        count += dub[k]*mul[k]
    return count

while True:
    N,M=map(int,input().split())
    if N==0: break
    sumH = [0]
    for _ in range(N):
        sumH += [sumH[-1]+int(input())]
    sumW=[0]
    for _ in range(M):
        sumW += [sumW[-1]+int(input())]
    print(solve())

Submission status: Accepted

Solution code:
while True:
    N, M = map(int, input().split())

    if N == 0 and M == 0:
        break

    h = [int(input().replace("\r", "")) for _ in range(N)]
    w = [int(input().replace("\r", "")) for _ in range(M)]

    table = {}

    for i in range(N):
        tmp = 0
        for j in range(i, N):
            tmp += h[j]
            table[tmp] = table.get(tmp, 0) + 1

    ans = 0

    for i in range(M):
        tmp = 0
        for j in range(i, M):
            tmp += w[j]
            ans += table.get(tmp, 0)

    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
  
    tmp = [0]
    h_lst = []
    for _ in range(n):
      h = int(input())
      new = [i + h for i in tmp]
      h_lst.extend(new)
      tmp = [0] + new
    
    tmp = [0]
    w_lst = []
    for _ in range(m):
      w = int(input())
      new = [i + w for i in tmp]
      w_lst.extend(new)
      tmp = [0] + new
  
    h_count = Counter(h_lst)
    w_count = Counter(w_lst)
    ans = 0
    for k in h_count:
      ans += h_count[k] * w_count[k]
  
    ans -= h_count[0] * w_count[0]
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
while N:
    H = [int(input()) for _ in range(N)]
    W = [int(input()) for _ in range(M)]

    HC = defaultdict(int)
    WC = defaultdict(int)

    Q = []
    for h in H:
        Q2 = [h]
        HC[h] += 1
        for q in Q:
            HC[h+q] += 1
            Q2.append(h+q)
        Q = Q2

    Q = []
    for w in W:
        Q2 = [w]
        WC[w] += 1
        for q in Q:
            WC[w+q] += 1
            Q2.append(w+q)
        Q = Q2

    ans = 0
    for k, v in HC.items():
        ans += v*WC[k]
    print(ans)

    N, M = map(int, input().split())

Submission status: Accepted

Solution code:
import itertools as it

def horizontal_input(T=str):
    return list(map(T,input().split()))

def vertical_input(n,T=str,sep=False,septype=tuple):
    data=[]
    if sep:
        for i in range(n):
            data.append(septype(map(T,input().split())))
    else:
        for i in range(n):
            data.append(T(input()))
    return data

while 1:
    n,m=horizontal_input(int)
    if n==0 and m==0:
        break
    h=[0]+list(it.accumulate(vertical_input(n,int)))
    w=[0]+list(it.accumulate(vertical_input(m,int)))
    _h={}
    for i in range(n+1):
        for j in range(i+1,n+1):
            if h[j]-h[i] in _h:
                _h[h[j]-h[i]]+=1
            else:
                _h[h[j]-h[i]]=1
    _w={}
    for i in range(m+1):
        for j in range(i+1,m+1):
            if w[j]-w[i] in _w:
                _w[w[j]-w[i]]+=1
            else:
                _w[w[j]-w[i]]=1
    ans=0
    for k in _h.keys():
        ans+=_h[k]*(_w[k] if k in _w else 0)
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
 
while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    H = [int(input()) for _ in range(N)]
    W = [int(input()) for _ in range(M)]
    for i in range(1, N):
        H[i] += H[i-1]
    for i in range(1, N):
        W[i] += W[i-1]
    all_H = [H[j] - H[i] for i in range(N) for j in range(i+1, N)]
    all_H += H
    all_W = {}
    for i in range(M):
        for j in range(i+1, M):
            if all_W.get(W[j] - W[i]) is not None:
                all_W[W[j] - W[i]] += 1
            else:
                all_W[W[j] - W[i]] = 1
            
    for i in range(M):
        if all_W.get(W[i]) is not None:
            all_W[W[i]] += 1
        else:
            all_W[W[i]] = 1
        
    ans = 0
    for i in all_H:
        ans += all_W[i]
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
 
while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    H = [int(input()) for _ in range(N)]
    W = [int(input()) for _ in range(M)]
    for i in range(1, N):
        H[i] += H[i-1]
    for i in range(1, M):
        W[i] += W[i-1]
    all_H = [H[j] - H[i] for i in range(N) for j in range(i+1, N)]
    all_H += H
    all_W = {}
    for i in range(M):
        for j in range(i+1, M):
            if all_W.get(W[j] - W[i]) is not None:
                all_W[W[j] - W[i]] += 1
            else:
                all_W[W[j] - W[i]] = 1
            
    for i in range(M):
        if all_W.get(W[i]) is not None:
            all_W[W[i]] += 1
        else:
            all_W[W[i]] = 1
        
    ans = 0
    for i in all_H:
        ans += all_W[i]
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
 
while True:
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    H = [int(input()) for _ in range(N)]
    W = [int(input()) for _ in range(M)]
    for i in range(1, N):
        H[i] += H[i-1]
    for i in range(1, M):
        W[i] += W[i-1]
    all_H = [H[j] - H[i] for i in range(N) for j in range(i+1, N)]
    all_H += H
    all_W = {}
    for i in range(M):
        for j in range(i+1, M):
            if all_W.get(W[j] - W[i]) is not None:
                all_W[W[j] - W[i]] += 1
            else:
                all_W[W[j] - W[i]] = 1
            
    for i in range(M):
        if all_W.get(W[i]) is not None:
            all_W[W[i]] += 1
        else:
            all_W[W[i]] = 1
        
    ans = 0
    for i in all_H:
        ans += all_W.get(i)
    print(ans)

Submission status: Runtime Error

Solution code:
while 1:
    N,M = map(int,raw_input().split())
    if N == 0: break
    h = [int(raw_input()) for _ in range(N)]
    w = [int(raw_input()) for _ in range(M)]
    ans = 0
    H,W = h[:],w[:]
    for i in range(N):
        s = h[i]
        for j in range(i+1,N):
            s += h[j]
            H.append(s)
    for i in range(M):
        s = w[i]
        for j in range(i+1,N):
            s += w[j]
            W.append(s)
    for hi in H:
        for wi in W:
                if hi == wi: ans += 1
    print ans

Submission status: Runtime Error

Solution code:
while 1:
    N,M = map(int,raw_input().split())
    if N == 0: break
    h = [int(raw_input()) for _ in range(N)]
    w = [int(raw_input()) for _ in range(M)]
    ans = 0
    H,W = h[:],w[:]
    for i in range(N):
        s = h[i]
        for j in range(i+1,N):
            s += h[j]
            H.append(s)
    for i in range(M):
        s = w[i]
        for j in range(i+1,M):
            s += w[j]
            W.append(s)
    for hi in H:
        for wi in W:
                if hi == wi: ans += 1
    print ans

Submission status: Runtime Error

Solution code:
while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    else:
        H=[]
        W=[]
        for i in range(N):
            H.append(int(raw_input()))
        for i in range(M):
            W.append(int(raw_input()))
        S=0
        for top in range(N):
            for left in range(M):
                h=0
                w=0
                right=left
                for bottom in range(top,N):
                    h=h+H[bottom]
                    while w<h and right<M:
                        w=w+W[right]
                        right=right+1
                    if w==h:
                        S=S+1
        print S

Submission status: Runtime Error

Solution code:
from math import log
class SegmentTree :
	def __init__ (self, N):
		self.N = N
		self.tree = [0 for i in range(2 * N - 1)]

	def update(self,i,x):
		node = i + self.N - 1
		self.tree[node] += x
		while node > 0:
			node = (node-1) / 2
			self.tree[node] += x

	def sum(self,here,l,r,hl,hr): #init : hl = 0, hr = N = 2 ** x - 1
		if here >= self.N - 1 or l == hl and r == hr:
			return self.tree[here]
		midle = (hl + hr + 1) / 2 # belong to rchild
		result = 0
		if l < midle :
			result += self.sum(2 * here + 1, l, min(r,midle - 1), hl, midle - 1) 
		if r >= midle :
			result += self.sum(2 * here + 2, max(l,midle), r, midle, hr) 
		return result
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon_idx = log(n,2)
	Lat_idx = log(m,2)
	LonN = 2 ** (int(Lon_idx) if Lon_idx.is_integer() else (int(Lon_idx)+1))
	LatN = 2 ** (int(Lat_idx) if Lat_idx.is_integer() else (int(Lat_idx)+1))
	LonST = SegmentTree(LonN)
	LatST = SegmentTree(LatN)
	for i in range(0,n):
		LonST.update(i,int(raw_input()))
	for i in range(0,m):
		LatST.update(i,int(raw_input()))
	Lon = [0 for i in range(n*1000+1)]
	Lat = [0 for i in range(m*1000+1)]
	for i in range(1,n+1):
		for j in range(n+1-i):
			Lon[LonST.sum(0,j,j+i-1,0,LonN-1)]+=1
	for i in range(1,m+1):
		for j in range(m+1-i):
			Lat[LatST.sum(0,j,j+i-1,0,LatN-1)]+=1
	max_width = min(LonST.tree[0],LatST.tree[0])
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N,M = map(int,input().split())
    if N == 0 and M == 0:
        break
    square_count_w = [0 for i in range(1000*1500+1)]
    square_count_h = [0 for i in range(1000*1500+1)]
    heights = []
    widths = []

    for i in range(N):
        height = int(input())
        square_count_h[height] += 1
        for h in heights[::-1]:
            square_count_h[height+h] += 1
        heights.append(height)

    for i in range(M):
        width = int(input())
        square_count_w[width] += 1
        for w in widths[::-1]:
            square_count_w[width+w] += 1
        widths.append(width)

    ans = 0
    for i in range(1000*1500+1):
        ans += square_count_w[i] * square_count_h[i]

    print(ans)

Submission status: Runtime Error

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (1000 * 1000)
    wl = [0] * (1000 * 1000)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans

Submission status: Runtime Error

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if N == 0 and M == 0: break
    h = [input() for _ in range(N)]
    for i in range(N-1):
        h[i+1] += h[i]
    w = [input() for _ in range(M)]
    for i in range(M-1):
        w[i+1] += w[i]
    h = [0] + h
    w = [0] + w
    hl = [0] * (1000 * 1000 + 1)
    wl = [0] * (1000 * 1000 + 1)
    for i in range(N):
        for j in range(i+1, N+1):
            hl[h[j]-h[i]] += 1
    for i in range(M):
        for j in range(i+1, M+1):
            wl[w[j]-w[i]] += 1

    ans = 0
    for i, j in zip(hl, wl):
        ans += i*j
    print ans

Submission status: Runtime Error

Solution code:
while True:
    N, M = map(int, input().split())
    if N == M == 0:
        break

    L = []
    C = []
    for i in range(N):
        L.append(int(input()))
    for i in range(M):
        C.append(int(input()))
    for i in range(2, N+1):
        sL = []
        for j in range(N + 1 - i):
            sL.append(sum(L[j:i+j]))
        L += sL
    for i in range(2, M+1):
        sC = []
        for j in range(M +1 - i):
            sC.append(sum(C[j:i+j]))
        C += sC
    count = 0
    for x in C:
        for y in L:
            if x == y:
                count += 1
    print(count)

Submission status: Runtime Error

Solution code:
while True:
    N, M = map(int, input().split())
    if N == M == 0:
        break

    L = []
    C = []
    dL = {}
    count = 0
    
    for i in range(N):
        l = int(input())
        L.append(l)
        if not l in dL:
            dL[l] = 1
        else:
            dL[l] += 1

    sL = []
    for i in range(2, N+1):
        
        for j in range(N + 1 - i):
            l = sum(L[j:i+j])
            if not l in dL:
                dL[l] = 1
            else:
                dL[l] += 1
    for i in range(M):
        c = int(input())
        C.append(c)
        if c in dL:
            count += dL[c]
        
    for i in range(2, M+1):
        for j in range(M +1 - i):
            c = sum(C[j:i+j])
            if c in dL:
                count += dL[c]

    print(count)

Submission status: Runtime Error

Solution code:
import collections
cnt1=collections.Counter()
cnt2=collections.Counter()
n,m=map(int, input().split())
ll=[0]*1500
for i in range(n):
    x=int(input())
    for j in range(i):
        ll[j]+=x
        cnt1[ll[j]]+=1

for i in range(m):
    x=int(input())
    for j in range(i):
        ll[j]+=x
        cnt2[ll[j]]+=1
sets=set(cnt1.keys().cnt2.keys())
ans=0
for s in sets:
    ans+=cnt1[s]*cnt2[s]
print(s)

Submission status: Runtime Error

Solution code:
import itertools
while True:
    N, M = map(int, input().split())
    if not N:
        break
    hs = [0] + [int(input()) for i in range(N)]
    ws = [0] + [int(input()) for i in range(M)]
    for i in range(N):
        hs[i + 1] += hs[i]
    for i in range(M):
        ws[i + 1] += ws[i]
    xs = sorted(map(lambda x: x[1] - x[0], itertools.combinations(hs, 2)))
    ys = sorted(map(lambda x: x[1] - x[0], itertools.combinations(ws, 2)))
    ans = 0
    for x in xs:
        ans += ys.count(x)
    print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from itertools import accumulate

buf = []
while True:
    n, m = int(input())
    if n == 0:
        break
    hs = [int(input()) for _ in range(n)]
    ws = [int(input()) for _ in range(m)]
    ha = accumulate(hs)
    wa = accumulate(ws)
    hd = defaultdict(int)
    wd = defaultdict(int)

    for i in range(n):
        for j in range(i + 1, n):
            hd[ha[j] - ha[i]] += 1
            wd[wa[j] - wa[i]] += 1
    ans = 0
    for h, cnt in hd.items():
        if h in wd:
            ans += cnt * wd[h]
    buf.append(ans)

print('\n'.join(map(str, buf)))

Submission status: Runtime Error

Solution code:
while True:
    n, m = map(int, input().split())
    if n == 0 and m == 0:
        break
    h = [0]
    for i in range(n):
        h.append(int(input()) + h[i])
    w = [0]
    for i in range(m):
        w.append(int(input()) + w[i])

    hList = [0] * 1000
    for i in range(n + 1):
        for j in range(i, n + 1):
            if i == j:
                continue
            else:
                hList[abs(h[i] - h[j])] += 1
    wList = [0] * 1000
    for i in range(m + 1):
        for j in range(i, m + 1):
            if i == j:
                continue
            else:
                wList[abs(w[i] - w[j])] += 1

    squareList = []
    for i in range(1000):
        squareList.append(hList[i] * wList[i])
    print(sum(squareList))

Submission status: Runtime Error

Solution code:
import math


def ans(N, M, h, w):
    count = 0
    for hr1 in range(N+1):
        for hr2 in range(N+1):
            if hr2 <= hr1: continue
            height = sum(h[e] for e in range(hr1, hr2))
            
            for wr1 in range(M+1):
                for wr2 in range(M+1):
                    if wr2 <= wr1: continue
                    width = sum(w[e] for e in range(wr1, wr2))
                    
                    if height == width:
                        count += 1
    return count
    
while True:
    N, M = [int(e) for e in input().strip().split()]
    if N == 0 and M == 0:
        break
    h = [int(input()) for e in range(N)]
    w = [int(input()) for e in range(M)]
    answer = ans(N,M,h,w)
    print(answer)

Submission status: Runtime Error

Solution code:
def ans(N, M, h, w):
    count = 0
    for hr1 in range(N+1):
        for hr2 in range(N+1):
            if hr2 <= hr1: continue
            height = sum(h[e] for e in range(hr1, hr2))
            
            for wr1 in range(M+1):
                for wr2 in range(M+1):
                    if wr2 <= wr1: continue
                    width = sum(w[e] for e in range(wr1, wr2))
                    
                    if height == width:
                        count += 1
    return count
    
while True:
    N, M = [int(e) for e in input().strip().split()]
    if N == 0 and M == 0:
        break
    h = [int(input()) for e in range(N)]
    w = [int(input()) for e in range(M)]
    answer = ans(N,M,h,w)
    print(answer)

Submission status: Runtime Error

Solution code:
def ans(N, M, h, w):
    count = 0
    for hr1 in range(N+1):
        for hr2 in range(N+1):
            if hr2 <= hr1: continue
            height = sum(h[e] for e in range(hr1, hr2))
             
            for wr1 in range(M+1):
                for wr2 in range(M+1):
                    if wr2 <= wr1: continue
                    width = sum([w[e] for e in range(wr1, wr2)])
                     
                    if height == width:
                        count += 1
    return count
     
while True:
    N, M = [int(e) for e in input().strip().split()]
    if N == 0 and M == 0:
        break
    h = [int(input()) for e in range(N)]
    w = [int(input()) for e in range(M)]
    answer = ans(N,M,h,w)
    print(answer)