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: 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:
while(True):
    tmp = list(map(int,input().split()))
    N, M = tmp[0],tmp[1]
    if N == 0:
        quit()
    hs = [0]
    ws = [0]
    hlen = []
    wlen = []
    ans = 0
    for i in range(N):
        hs.append(hs[-1] + int(input()))
    for i in range(M):
        ws.append(ws[-1] + int(input()))
    for i in range(N):
        for j in range(i+1,N+1):
            hlen.append(hs[j]-hs[i])
    for i in range(M):
        for j in range(i+1,M+1):
            wlen.append(ws[j]-ws[i])
    for i in hlen:
        ans += wlen.count(i)
    print(ans)

Submission status: Runtime Error

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):
        for j in range(i + 1, N + 1):
            HD[sum(H[i:j])] += 1
    ans = 0
    W = [int(input()) for i in range(M)]
    for i in range(M):
        for j in range(i + 1, M + 1):
            ans += HD[sum(W[i:j])]
    print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
while (n != 0 or m != 0):
    nlist = [] 
    mlist = []
    for i in range(n):
        t = int(input()) 
        nlist.append(t) 
    for i in range(m): 
        t = int(input())
        mlist.append(t)
    nsum = [] 
    for i in range(n):
        for k in range(n-i):
            c = 0 
            for l in range(i+1):
                c += nlist[k+l]
            nsum.append(c)
    msum = [] 
    for i in range(m): 
        for k in range(m-i):
            c = 0
            for l in range(i+1):
                c += mlist[k+l]
            msum.append(c)
    count = 0
    for i in nsum:
        count += msum.count(i)
    print(count) 
    n,m = map(int, input().split())

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
while (n != 0 or m != 0):
    nlist = [int(input())for i in range(n)]
    mlist = [int(input())for i in range(m)]
    nsum = [] 
    for i in range(n):
        for k in range(n-i):
            c = 0 
            for l in range(i+1):
                c += nlist[k+l]
            nsum.append(c)
    count = 0
    for i in range(m):
        for k in range(m-i):
            c = 0
            for l in range(i+1):
                c += mlist[k+l]
            if (c in nsum):
                count += nsum.count(c)       
    print(count) 
    n,m = map(int, input().split())

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
while (n != 0 or m != 0):
    nlist = [0]
    mlist = [0]
    for i in range(n):
        nlist += [nlist[-1] + int(input())]
    for i in range(m):
        mlist += [mlist[-1] + int(input())]
    nsum = []
    msum = []
    
    for i in range(n):
        for k in range(i+1,n+1):
            c = nlist[k] - nlist[i]
            nsum.append(c)
    for i in range(m):
        for k in range(i+1,m+1):
            c = mlist[k] - mlist[i]
            msum.append(c)
    count = 0
    for i in nsum:
        count += msum.count(i)
    print(count) 
    n,m = map(int, input().split())

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
while (n != 0 or m != 0):
    nlist = [0]
    mlist = [0]
    for i in range(n):
        nlist += [nlist[-1] + int(input())]
    for i in range(m):
        mlist += [mlist[-1] + int(input())]
    nsum = []
    msum = []
    count = 0
    for i in range(n):
        for k in range(i+1,n+1):
            c = nlist[k] - nlist[i]
            nsum.append(c)
    for i in range(m):
        for k in range(i+1,m+1):
            c = mlist[k] - mlist[i]
            if (c in nsum):
                count += nsum.count(c)
    print(count) 
    n,m = map(int, input().split())

Submission status: Runtime Error

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())]
    nsum = []
    msum = []
    count = 0
    for i in range(n):
        for k in range(i+1,n+1):
            c = nlist[k] - nlist[i]
            nsum.append(c)
    for i in range(m):
        for k in range(i+1,m+1):
            c = mlist[k] - mlist[i]
            if (c in nsum):
                count += nsum.count(c)
    print(count)

Submission status: Runtime Error

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)
    
    for i in xrange(N):
        for j in xrange(i + 1, N + 1):
            vertical[sum(road_v[i:j])] += 1
    for i in xrange(M):
        for j in xrange(i + 1, M + 1):
            lateral[sum(road_l[i:j])] += 1
    result = 0
    for v in vertical:
        result += vertical[v] * lateral[v]
    print result

Submission status: Runtime Error

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)
    
    for i in xrange(N):
        for j in xrange(i + 1, N + 1):
            vertical[sum(road_v[i:j])] += 1
    for i in xrange(M):
        for j in xrange(i + 1, M + 1):
            lateral[sum(road_l[i:j])] += 1

Submission status: Runtime Error

Solution code:
import sys
import math

while True:
    N, M = map(int, sys.stdin.readline().split())
    if N == 0:
        break
    vertical = {}
    lateral = {}
    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)
    
    for i in xrange(N):
        for j in xrange(i + 1, N + 1):
            temp = sum(road_v[i:j])
            vertical[temp] = vertical.setdefault(temp, 0) + 1
    for i in xrange(M):
        for j in xrange(i + 1, M + 1):
            temp = sum(road_l[i:j])
            lateral[temp] = lateral.setdefault(temp, 0) + 1
    result = 0
    for v in vertical:
        result += vertical[v] * lateral[v]
    print result

Submission status: Runtime Error

Solution code:
import sys
import math

while True:
    N, M = map(int, sys.stdin.readline().split())
    if N == 0:
        break
    vertical = {}
    lateral = {}
    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)
    
    for i in xrange(N):
        for j in xrange(i + 1, N + 1):
            temp = sum(road_v[i:j])
            if temp in vertical:
                vertical[temp] += 1
            else:
                vertical[temp] = 1
    for i in xrange(M):
        for j in xrange(i + 1, M + 1):
            temp = sum(road_l[i:j])
            if temp in lateral:
                lateral[temp] = lateral[temp] + 1
            else:
                lateral[temp] = 1
    result = 0
    for v in vertical:
        result += vertical[v] * lateral[v]
    print result

Submission status: Runtime Error

Solution code:
import sys
import math

while True:
    N, M = map(int, sys.stdin.readline().split())
    if N == 0:
        break
    vertical = {}
    lateral = {}
    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)
    
    for i in xrange(N):
        for j in xrange(i + 1, N + 1):
            temp = sum(road_v[i:j])
            if temp in vertical:
                vertical[temp] += 1
            else:
                vertical[temp] = 1
    for i in xrange(M):
        for j in xrange(i + 1, M + 1):
            temp = sum(road_l[i:j])
            if temp in lateral:
                lateral[temp] = lateral[temp] + 1
            else:
                lateral[temp] = 1
    result = 0
    for v in vertical:
        result += vertical[v] * lateral[v]
    print result
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys
import math

while True:
    N, M = map(int, sys.stdin.readline().split())
    if N == 0:
        break
    vertical = {}
    lateral = {}
    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)
    
    for i in xrange(N):
        for j in xrange(i + 1, N + 1):
            temp = sum(road_v[i:j])
            if temp in vertical:
                vertical[temp] += 1
            else:
                vertical[temp] = 1
    for i in xrange(M):
        for j in xrange(i + 1, M + 1):
            temp = sum(road_l[i:j])
            if temp in lateral:
                lateral[temp] = lateral[temp] + 1
            else:
                lateral[temp] = 1
    result = 0
    for v in vertical:
        if v in lateral:
            result += vertical[v] * lateral[v]
    print result

Submission status: Runtime Error

Solution code:
from collections import Counter

def add(s, tw):
    if tw in s:
        s[tw] += 1
    else:
        s[tw] = 1

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

    for i in range(n):
        t = s = input()
        add(ws, s)
        for pw in reversed(w):
            s+=pw
            add(ws, s)
        w.append(t)

    for i in range(m):
        t = s = input()
        add(hs, s)
        for pw in reversed(h):
            s+=pw
            add(hs, s)
        h.append(t)

    ans = 0
    for w, wn in ws.iteritems():
        for h, hn in hs.iteritems():
            if w == h:
                ans += wn * hn

    print ans

Submission status: Runtime Error

Solution code:
from collections import defaultdict

while 1:
    ws, hs, w, h = defaultdict(lambda:0), defaultdict(lambda:0), [], []
    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)

    ans = 0
    for w, wn in ws.iteritems():
        for h, hn in hs.iteritems():
            if w == h:
                ans += wn * hn
    print ans