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: Wrong Answer

Solution code:
from collections import defaultdict

def getArray(a):
    d = defaultdict(int)
    n = len(a)
    for i in range(n):
        s = 0
        for j in range(i,n):
            s += a[i]
            d[s] += 1
    return d

while 1:
    N,M = map(int,raw_input().split())
    if N == 0: break
    h = [int(raw_input()) for _ in xrange(N)]
    w = [int(raw_input()) for _ in xrange(M)]
    H,W = getArray(h),getArray(w)
    print sum(H[hi]*W[hi] for hi in H)

Submission status: Wrong Answer

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for _ in range(1000 * n + 1)]
	Lat = [0 for _ in range(1000 * m + 1)]
	Lon_sum = []
	Lat_sum = []
	for _ in range(0,n):
		h = int(raw_input())
		Lon_sum = [h + j for j in Lon_sum] + [h]
		for j in Lon_sum[1:]:
			Lon[j] += 1
	for _ in range(0,m):
		w = int(raw_input())
		Lat_sum = [w + j for j in Lat_sum] + [w]
		for j in Lat_sum:
			Lat[j] += 1
	max_width = min(Lon_sum[0],Lat_sum[0])
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Wrong Answer

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

import collections

while True:
    N,M = map(int,input().split())
    if N == 0 and M == 0:
        break
    square_count_w = collections.defaultdict(int)
    square_count_h = collections.defaultdict(int)
    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 key,value in square_count_w.items():
        ans += square_count_w[key] * square_count_h[key]

    print(ans)

Submission status: Wrong Answer

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

import collections

while True:
    N,M = map(int,raw_input().split())
    if N == 0 and M == 0:
        break
    square_count_w = collections.defaultdict(int)
    square_count_h = collections.defaultdict(int)
    heights = []
    widths = []

    for i in range(N):
        height = int(raw_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(raw_input())
        square_count_w[width] += 1
        for w in widths[::-1]:
            square_count_w[width+w] += 1
        widths.append(width)

    ans = 0
    for key,value in square_count_w.items():
        ans += square_count_w[key] * square_count_h[key]

    print(ans)

Submission status: Wrong Answer

Solution code:
print("hello world")

Submission status: Wrong Answer

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 = "hoge"
    print(answer, N, M, h, w)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m = LI()
        if n == 0 and m == 0:
            break
        a = [I() for _ in range(n)]
        b = [I() for _ in range(m)]
        ar = [0] * (n+1)
        for i in range(n):
            ar[i+1] = a[i] + a[i]
        ad = collections.defaultdict(int)
        for i in range(n+1):
            for j in range(i+1,n+1):
                ad[ar[j]-ar[i]] += 1
        br = [0] * (m+1)
        for i in range(m):
            br[i+1] = b[i] + b[i]
        bd = collections.defaultdict(int)
        for i in range(m+1):
            for j in range(i+1,m+1):
                bd[br[j]-br[i]] += 1

        r = 0
        for k in ad.keys():
            r += ad[k] * bd[k]

        rr.append(r)



    return '\n'.join(map(str, rr))


print(main())

Submission status: Wrong Answer

Solution code:
def solve(lis_height,lis_width):
    h=len(lis_height)
    w=len(lis_width)
    dic = {}
    for i in range(h):
        k=0
        for j in range(i,h):
            k+=lis_height[j]
            if k in dic:
                dic[k]+=1
            else:
                dic[k]=1
    ans = 0
    for i in range(w):
        k=0
        for j in range(j,w):
            k+=lis_width[j]
        if k in dic:
            ans += dic[k]

    print(ans)


while True:
    h,w=[int(i) for i in input().split(' ')]
   # print(a)
    if h == 0:
        break
    lis_h =[]
    lis_w=[]
    for i in range(h):
        lis_h.append(int(input()))
    for i in range(w):
        lis_w.append(int(input()))

    solve(lis_h,lis_w)

Submission status: Wrong Answer

Solution code:
import collections

c = collections.Counter()

c[0] += 1
c[1] += 2

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections

while True:
    N, M = map(int, sys.stdin.readline().split())
    if N == 0:
        break
    vertical = collections.Counter()
    lateral = collections.Counter()
    road_v = []
    road_l = []
    for i in xrange(N):
        h = int(raw_input())
        road_v.append(h)
    for i in xrange(M):
        w = int(raw_input())
        road_l.append(w)

Submission status: Time Limit Exceeded

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)]
    all_H = []
    all_W = []
    for i in range(N):
        for j in range(i + 1, N + 1):
            all_H.append(sum(H[i:j]))
    for i in range(M):
        for j in range(i + 1, M + 1):
            all_W.append(sum(W[i:j]))
    all_H = Counter(sorted(all_H))
    all_W = Counter(sorted(all_W))

    ans = 0
    for k, v in all_H.items():
        if k in all_H:
            ans += v * all_W[k]
    # print(all_H)
    # print(all_W)
    print(ans)

Submission status: Time Limit Exceeded

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)]
    all_H = Counter(
        sorted([sum(H[i:j]) for i in range(N) for j in range(i + 1, N + 1)])
    )
    all_W = Counter(
        sorted([sum(W[i:j]) for i in range(M) for j in range(i + 1, M + 1)])
    )
    ans = 0
    for k, v in all_H.items():
        if k in all_H:
            ans += v * all_W[k]
    print(ans)

Submission status: Memory Limit Exceeded

Solution code:

def SQ(N,M):
    x=0
    y=0
    h=[0]
    w=[0]
    for i in range(N):
        x+=int(input())
        h.append(x)
    for i in range(M):
        y+=int(input())
        w.append(y)
    crossing=[[0 for i in range(y+1)] for j in range(x+1)]
    for i in range(N+1):
        for j in range(M+1):
            crossing[h[i]][w[j]]=1

    answer=0
    for i in range(N+1):
        for j in range(M+1):
            for k in range(1,x+y+2):
                if h[i]-k>=0 and w[j]-k>=0:
                    if crossing[h[i]-k][w[j]-k]==1:
                        answer+=1
                    else:
                        pass
                else:
                    break

    print(answer)

while True:
    NM=input().split()
    N=int(NM[0])
    M=int(NM[1])
    if N==0 and M==0:
        break
    else:
        SQ(N,M)

Submission status: Accepted

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)]

    all_H = []
    for i in range(N):
        s = 0
        for j in range(i, N):
            s += H[j]
            all_H.append(s)

    all_W = []
    for i in range(M):
        s = 0
        for j in range(i, M):
            s += W[j]
            all_W.append(s)

    all_H = Counter(all_H)
    all_W = Counter(all_W)
    ans = 0
    for k, v in all_H.items():
        if k in all_H:
            ans += v * all_W[k]
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
while 1:
  h,w=map(int,input().split())
  if h==w==0:break
  xs,ys=[0],[0]
  for _ in range(h):ys+=[ys[-1]+int(input())]
  for _ in range(w):xs+=[xs[-1]+int(input())]
  print(sum(c*c-c for c in Counter(x-y for y in ys for x in xs).values())//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

def getArray(a):
    d = defaultdict(int)
    n = len(a)
    for i in range(n):
        s = 0
        for j in range(i,n):
            s += a[j]
            d[s] += 1
    return d

while 1:
    N,M = map(int,raw_input().split())
    if N == 0: break
    h = [int(raw_input()) for _ in xrange(N)]
    w = [int(raw_input()) for _ in xrange(M)]
    H,W = getArray(h),getArray(w)
    print sum(H[hi]*W[hi] for hi in H)

Submission status: Accepted

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for i in range(1000 * n + 1)]
	Lat = [0 for i in range(1000 * m + 1)]
	Lon_sum = [0]
	Lat_sum = [0]
	for i in range(0,n):
		tmp_Lon_sum = [0]
		h = int(raw_input())
		for j in Lon_sum:
			Lon[j+h] += 1
			tmp_Lon_sum.append(j+h) 
		Lon_sum = tmp_Lon_sum
	else :
		Lon_max = Lon_sum[-1]
	for i in range(0,m):
		tmp_Lat_sum = [0]
		w = int(raw_input())
		for j in Lat_sum:
			Lat[j+w] += 1
			tmp_Lat_sum.append(j+w) 
		Lat_sum = tmp_Lat_sum
	else :
		Lat_max = Lat_sum[-1]
	max_width = min(Lon_max,Lat_max)
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Accepted

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for i in range(1000 * n + 1)]
	Lat = [0 for i in range(1000 * m + 1)]
	Lon_sum = [0]
	Lat_sum = [0]
	for i in range(0,n):
		tmp_Lon_sum = [0]
		h = int(raw_input())
		for j in Lon_sum:
			Lon[j+h] += 1
			tmp_Lon_sum += [j+h] 
		Lon_sum = tmp_Lon_sum
	else :
		Lon_max = Lon_sum[-1]
	for i in range(0,m):
		tmp_Lat_sum = [0]
		w = int(raw_input())
		for j in Lat_sum:
			Lat[j+w] += 1
			tmp_Lat_sum += [j+w] 
		Lat_sum = tmp_Lat_sum
	else :
		Lat_max = Lat_sum[-1]
	max_width = min(Lon_max,Lat_max)
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Accepted

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for i in range(1000 * n + 1)]
	Lat = [0 for i in range(1000 * m + 1)]
	Lon_sum = [0]
	Lat_sum = [0]
	for i in range(0,n):
		h = int(raw_input())
		Lon_sum = [0] + [h + j for j in Lon_sum]
		for j in Lon_sum:
			Lon[j] += 1
	for i in range(0,m):
		w = int(raw_input())
		Lat_sum = [0] + [w + j for j in Lat_sum]
		for j in Lat_sum:
			Lat[j] += 1
		Lat_max = Lat_sum[-1]
	max_width = min(Lon_sum[-1],Lat_sum[-1])
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Accepted

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for i in range(1000 * n + 1)]
	Lat = [0 for i in range(1000 * m + 1)]
	Lon_sum = [0 for i in range(n)]
	Lat_sum = [0 for i in range(m)]
	for i in range(0,n):
		h = int(raw_input())
		for j in range(i+1):
			Lon_sum[j] += h
			Lon[Lon_sum[j]] += 1
	for i in range(0,m):
		tmp_Lat_sum = [0]
		w = int(raw_input())
		for j in range(i+1):
			Lat_sum[j] += w
			Lat[Lat_sum[j]] += 1
	max_width = min(Lon_sum[0],Lat_sum[0])
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Accepted

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for i in range(1000 * n + 1)]
	Lat = [0 for i in range(1000 * m + 1)]
	Lon_sum = []
	Lat_sum = []
	for i in range(0,n):
		h = input()
		Lon_sum = [h + j for j in Lon_sum] + [h]
		for j in Lon_sum:
			Lon[j] += 1
	for i in range(0,m):
		w = input()
		Lat_sum = [w + j for j in Lat_sum] + [w]
		for j in Lat_sum:
			Lat[j] += 1
	max_width = min(Lon_sum[0],Lat_sum[0])
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Accepted

Solution code:
while 1 :
	n, m = map(int,raw_input().split(" "))
	if (n, m) == (0,0):
		break
	Lon = [0 for _ in range(1000 * n + 1)]
	Lat = [0 for _ in range(1000 * m + 1)]
	Lon_sum = []
	Lat_sum = []
	for _ in range(0,n):
		h = int(raw_input())
		Lon_sum = [h + j for j in Lon_sum] + [h]
		for j in Lon_sum:
			Lon[j] += 1
	for _ in range(0,m):
		w = int(raw_input())
		Lat_sum = [w + j for j in Lat_sum] + [w]
		for j in Lat_sum:
			Lat[j] += 1
	max_width = min(Lon_sum[0],Lat_sum[0])
	print sum([Lon[i]*Lat[i] for i in range(1,max_width+1)])

Submission status: Accepted

Solution code:
import bisect
while(1):
    [N,M]=[int(x) for x in raw_input().split()]
    if N==0:
        break
    else:
        hlist=[]
        wlist=[]
        bef=[]
        for i in range(N):
            newh=int(raw_input())
            news=[newh+a for a in bef]
            hlist+=news
            hlist.append(newh)
            bef=news+[newh]
        bef=[]
        for i in range(M):
            neww=int(raw_input())
            news=[neww+a for a in bef]
            wlist+=news
            wlist.append(neww)
            bef=news+[neww]
        hlist.sort()
        #print hlist,wlist
        ans=0
        for w in wlist:
            ans+=bisect.bisect(hlist,w)-bisect.bisect_left(hlist,w)
        print ans

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
def cal_interval(Num):
	interval = ddict(int)
	dp = [0 for i in range(Num)]
	for i in range(Num):
		tmp = int(raw_input())
		for j in range(i+1):
			dp[j] += tmp
			interval[dp[j]] += 1
	return interval
while 1:
	N, M = map(int,raw_input().split(" "))
	if (N, M) == (0,0):
		break
	Lon = cal_interval(N)
	Lat = cal_interval(M)
	count = 0
	for k,v in Lon.iteritems():
		count += v * Lat[k]
	print count

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
def cal_interval(Num):
	interval = ddict(int)
	dp = [0 for i in range(Num)]
	for i in range(Num):
		tmp = int(raw_input())
		for j in range(i+1):
			dp[j] += tmp
			interval[dp[j]] += 1
	return interval
while 1:
	N, M = map(int,raw_input().split(" "))
	if (N, M) == (0,0):
		break
	Lon = cal_interval(N)
	Lat = cal_interval(M)
	print sum(v * Lat[k] for k,v in Lon.iteritems())

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
def cal_interval(Num):
	interval = ddict(int)
	dp = [0 for i in range(Num)]
	for i in range(Num):
		tmp = int(raw_input())
		for j in range(i+1):
			dp[j] += tmp
			interval[dp[j]] += 1
	return interval
while 1:
	N, M = map(int,raw_input().split(" "))
	if (N, M) == (0,0):
		break
	Lon = cal_interval(N)
	Lat = cal_interval(M)
	print sum(Lon[k] * Lat[k] for k in Lon if k in Lat)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
def cal_interval(Num):
	interval = ddict(int)
	dp = [int(raw_input()) for i in range(Num)]
	for i in range(Num):
		tmp = dp[i]
		interval[tmp] += 1
		for j in range(i):
			dp[j] += tmp
			interval[dp[j]] += 1
	return interval
while 1:
	N, M = map(int,raw_input().split(" "))
	if (N, M) == (0,0):
		break
	Lon = cal_interval(N)
	Lat = cal_interval(M)
	print sum(Lon[k] * Lat[k] for k in Lon if k in Lat)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddict
def cal_interval(Num):
	interval = ddict(int)
	dp = [int(raw_input()) for i in range(Num)]
	for i in range(Num):
		tmp = dp[i]
		interval[tmp] += 1
		for j in range(i):
			tmp += dp[i-j-1]
			interval[tmp] += 1
	return interval
while 1:
	N, M = map(int,raw_input().split(" "))
	if (N, M) == (0,0):
		break
	Lon = cal_interval(N)
	Lat = cal_interval(M)
	print sum(Lon[k] * Lat[k] for k in Lon if k in Lat)

Submission status: Accepted

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

import collections

while True:
    N,M = map(int,raw_input().split())
    if N == 0 and M == 0:
        break
    square_count_w = collections.defaultdict(int)
    square_count_h = collections.defaultdict(int)
    heights = []
    widths = []

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

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

    ans = 0
    for key,value in square_count_w.items():
        ans += square_count_w[key] * square_count_h[key]

    print(ans)

Submission status: Accepted

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] * (h[-1] + 1)
    wl = [0] * (w[-1] + 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: Accepted

Solution code:
from itertools import combinations
from collections import Counter

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

    L = [0]
    C = [0]
    x = 0
    y = 0
    count = 0
    
    for i in range(N):
        l = int(input())
        x += l
        L.append(x)

    dL = Counter([max(x1, x2) - min(x1 ,x2) for (x1, x2) in combinations(L, 2)])

    for i in range(M):
        c = int(input())
        y += c
        C.append(y)
    for y1, y2 in combinations(C, 2):
        dy = max(y1,y2)-min(y1,y2)
        if dy in dL:
            count += dL[dy]


    print(count)

Submission status: Accepted

Solution code:
import collections
while 1:
    cnt1=collections.Counter()
    cnt2=collections.Counter()
    n,m=map(int, input().split())
    if n+m==0:
        break
    ll=[0]*1500
    for i in range(n):
        x=int(input())
        for j in range(i+1):
            ll[j]+=x
            cnt1[ll[j]]+=1
    ll=[0]*1500
    for i in range(m):
        x=int(input())
        for j in range(i+1):
           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(ans)

Submission status: Accepted

Solution code:
import sys



def main():
    
    while True:
        n,m = map(int, sys.stdin.readline().split())
        if n == 0 and m == 0:
            break

        # input
        hs = []
        for i in range(n):
            h = int(sys.stdin.readline())
            hs.append(h)

        ws = []
        for i in range(m):
            w = int(sys.stdin.readline())
            ws.append(w)

        # bucket
        bhs = [0] * 1500010
        for i in range(n):
            sz = 0
            for j in range(i, n):
                sz += hs[j]
                bhs[sz] += 1
        
        ans = 0
        for i in range(m):
            sz = 0
            for j in range(i, m):
                sz += ws[j]
                ans += bhs[sz]

        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
while True:
    n, m = [int(_) for _ in raw_input().split()]
    if n == m == 0:
        break

    h = [int(raw_input()) for _ in xrange(n)]
    w = [int(raw_input()) for _ in xrange(m)]

    hs = {}

    for i in xrange(n):
        h0 = 0
        for j in xrange(i, n):
            h0 += h[j]
            hs[h0] = hs.get(h0, 0) + 1

    ans = 0

    for i in xrange(m):
        w0 = 0
        for j in xrange(i, m):
            w0 += w[j]
            ans += hs.get(w0, 0)

    print(ans)

Submission status: Accepted

Solution code:
N=[int(i) for i in input().split()]
while N[0]!=0 or N[1]!=0:
    h=[]
    for i in range(2):
        h.append([])
   #     print(N)
        for j in range(N[i]):
            h[i].append(int(input()))
     #       print(h)
        s=0
        for j in range(N[i]-1):
            s=h[i][j]
     #       print(j)
            for k in range(j+1,N[i]):
                s+=h[i][k]
          #      print(s)
                h[i].append(s)
        h[i].sort()
    b=0
    i=0
    j=0
    l0=len(h[0])
    l1=len(h[1])
    while i < l0:
        c=0
        while j < l1 and h[0][i]>=h[1][j]:
       #     print(i)
       #     print(j)
            if h[0][i]==h[1][j]:
                c+=1
            j+=1
        b+=c
        k=i+1
     #   print(h)
    #    print(l1)
        while k<l0 and h[0][i]==h[0][k]:
            b+=c
            k+=1
      #  print(k)
        i=k
    print(b)
    N=[int(i) for i in input().split()]

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import accumulate

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

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            hd[ha[j] - ha[i]] += 1
    for i in range(m + 1):
        for j in range(i + 1, m + 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: Accepted

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])

    hDict = {}
    for i in range(n + 1):
        for j in range(i, n + 1):
            if i == j:
                continue
            else:
                diff = abs(h[i] - h[j])
                if diff in hDict:
                    hDict[diff] += 1
                else:
                    hDict[diff] = 1
    wDict = {}
    for i in range(m + 1):
        for j in range(i, m + 1):
            if i == j:
                continue
            else:
                diff = abs(w[i] - w[j])
                if diff in wDict:
                    wDict[diff] += 1
                else:
                    wDict[diff] = 1

    ans = 0
    for diff in hDict.keys():
        if diff in wDict:
            ans += hDict[diff] * wDict[diff]
    print(ans)

Submission status: Accepted

Solution code:
while(True):
    tmp = list(map(int,input().split()))
    n,m = tmp[0],tmp[1]
    ans = 0
    if n == 0:
        quit()
    hs, ws = [0], [0]
    #hとwについて累積和を取る
    for i in range(n):
        hs.append(hs[-1]+int(input()))
    for i in range(m):
        ws.append(ws[-1]+int(input()))
    #hとwの差分を記録
    h_dif, w_dif = [0] * (hs[-1]+1), [0] * (ws[-1]+1)
    for i in range(n):
        for j in range(i+1,n+1):
            h_dif[hs[j]-hs[i]] += 1
    for i in range(m):
        for j in range(i+1,m+1):
            w_dif[ws[j]-ws[i]] += 1
    for i in range(1,min(len(h_dif),len(w_dif))):
        ans += h_dif[i] * w_dif[i]
    print(ans)

Submission status: Accepted

Solution code:
#問題番号：2015 「Square Route」
#教室内の着席位置：中央*奥
#URL：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2015
#この問題の制約を見るに、O(N^2)で十分
#しかし、道と道の間の長さがN(N-1)/2あるため、これを求めるだけでO(N^2)
#従って、hとwでの比較はO(N)でしなければならない
while(True):
    tmp = list(map(int,input().split()))
    n,m = tmp[0],tmp[1]
    ans = 0
    #終了するケースを省く
    if n == 0:
        quit()
    hs, ws = [0], [0]
    #hとwについて累積和を取る(これがhsとws)
    for i in range(n):
        hs.append(hs[-1]+int(input()))
    for i in range(m):
        ws.append(ws[-1]+int(input()))
    #hとwについて、道の間の距離を差分として計算してそれぞれ記録(累積和を取っているのでsumを取る必要がなく高速)
    #工夫として、距離を直接記録して行くのではなく、「距離Lになった時にdif[L]をインクリメント」という方針
    #こうすることで最終的な計算をsum(h_dif[L]*w_dif[L])で出せる
    h_dif, w_dif = [0] * (hs[-1]+1), [0] * (ws[-1]+1)
    for i in range(n):
        for j in range(i+1,n+1):
            h_dif[hs[j]-hs[i]] += 1
    for i in range(m):
        for j in range(i+1,m+1):
            w_dif[ws[j]-ws[i]] += 1
    for i in range(1,min(len(h_dif),len(w_dif))):
        ans += h_dif[i] * w_dif[i]
    print(ans)

Submission status: Accepted

Solution code:
while(1):
    N, M = map(int, input().split())
    if N == 0 and M == 0:
        break
    H = [int(input()) for i in range(N)]
    HD = [0] * 1500 ** 2
    for i in range(N):
        tmp = 0
        for j in range(i, N):
            tmp += H[j]
            HD[tmp] += 1
    ans = 0
    W = [int(input()) for i in range(M)]
    for i in range(M):
        tmp = 0
        for j in range(i, M):
            tmp += W[j]
            ans += HD[tmp]
    print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m = LI()
        if n == 0 and m == 0:
            break
        a = [I() for _ in range(n)]
        b = [I() for _ in range(m)]
        ar = [0] * (n+1)
        for i in range(n):
            ar[i+1] = ar[i] + a[i]
        ad = collections.defaultdict(int)
        for i in range(n+1):
            for j in range(i+1,n+1):
                ad[ar[j]-ar[i]] += 1
        br = [0] * (m+1)
        for i in range(m):
            br[i+1] = br[i] + b[i]
        bd = collections.defaultdict(int)
        for i in range(m+1):
            for j in range(i+1,m+1):
                bd[br[j]-br[i]] += 1

        r = 0
        for k in ad.keys():
            r += ad[k] * bd[k]

        rr.append(r)



    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
while True:
    n,m = map(int, input().split())
    if n == 0 and m == 0:
        break
    else:
        h,w = [],[]

        for _ in range(n):
            h.append(int(input()))

        for _ in range(m):
            w.append(int(input()))

        l = [0 for _ in range(1000*1501)]

        for i in range(n):
            tmp = 0
            for j in range(i,n):
                tmp += h[j]
                l[tmp] += 1

        ans = 0

        for i in range(m):
            tmp = 0
            for j in range(i,m):
                tmp += w[j]
                ans += l[tmp]

        print(ans)

Submission status: Accepted

Solution code:
def solve(lis_height,lis_width):
    h=len(lis_height)
    w=len(lis_width)
    dic = {}
    for i in range(h):
        k=0
        for j in range(i,h):
            k+=lis_height[j]
            if k in dic:
                dic[k]+=1
            else:
                dic[k]=1
    ans = 0
    #print(dic)
    #print(w,'a')
    for i in range(w):
        k=0
        for j in range(i,w):
            k+=lis_width[j]
           # print(j)
            if k in dic:
                ans += dic[k]
                #print(k,dic[k])

    print(ans)


while True:
    h,w=[int(i) for i in input().split(' ')]
   # print(a)
    if h == 0:
        break
    lis_h =[]
    lis_w=[]
    for i in range(h):
        lis_h.append(int(input()))
    for i in range(w):
        lis_w.append(int(input()))

    solve(lis_h,lis_w)

Submission status: Accepted

Solution code:
while True:
    n,m = map(int, input().split())
    if n == 0 and m == 0:
        break
    nlist = [0]
    mlist = [0]
    for i in range(n):
        nlist += [nlist[-1] + int(input())]
    for i in range(m):
        mlist += [mlist[-1] + int(input())]

    l = [0for i in range(1000*1501)]
    for i in range(n):
        t = 0
        for k in range(i+1,n+1):
            t = nlist[k] - nlist[i]
            l[t] += 1
    count = 0
    for i in range(m):
        for k in range(i+1,m+1):
            t = mlist[k] - mlist[i]
            count += l[t]
    
    print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    H=[input() for i in range(N)]
    W=[input() for i in range(M)]
    dh=defaultdict(int)
    dw=defaultdict(int)
    for i in range(N):
        s=H[i]
        dh[s]+=1
        for j in range(i+1,N):
            s+=H[j]
            dh[s]+=1
    for i in range(M):
        s=W[i]
        dw[s]+=1
        for j in range(i+1,M):
            s+=W[j]
            dw[s]+=1
    print sum(dh[h]*dw[h] for h in dh if h in dw)

Submission status: Accepted

Solution code:
from collections import defaultdict
def getDic(L,n):
    d=defaultdict(int)
    for i in range(n):
        s=L[i]
        d[s]+=1
        for j in range(i+1,n):
            s+=L[j]
            d[s]+=1
    return d

while True:
    N,M=map(int,raw_input().split())
    if N==M==0:break
    H=[input() for i in range(N)]
    W=[input() for i in range(M)]
    dh=getDic(H,N)
    dw=getDic(W,M)
    print sum(dh[h]*dw[h] for h in dh if h in dw)