Problem:


Score : 700 points

Problem Statement

There are some coins in the xy-plane.
The positions of the coins are represented by a grid of characters with H rows and W columns.
If the character at the i-th row and j-th column, s_{ij}, is #, there is one coin at point (i,j); if that character is ., there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold.
There is also no coin at point (x,y) where x or y (or both) is not an integer.
Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.

Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|.
Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

1 \leq H,W \leq 300

s_{ij} is # or ..

Input

Input is given from Standard Input in the following format:

H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}

Output

Print the number of triples that satisfy the condition.

Sample Input 1

5 4
#.##
.##.
#...
..##
...#

Sample Output 1

3

((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) and ((1,3),(3,1),(4,4)) satisfy the condition.

Sample Input 2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####

Sample Output 2

870



Sample input:
5 4
#.##
.##.
#...
..##
...#


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p,W+p),np.int64)
    diag[:H,:W] += S
    for n in range(1,H+p):
        diag[n,:W] += diag[n-1,1:W+1]
    for h,w in itertools.product(range(H),range(W)):
        n = h if h<w else w
        L = S[h,w-1::-1][:n]
        U = S[h-1::-1,w][:n]
        RD = diag[h+1:h+n+1,w] - diag[h,w+1:w+n+1]
        cnt += (L*U*RD).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

S = np.pad(S,(p,p),'constant').astype(np.int64)

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p+p,W+p+p),np.int64)
    for n in range(p,H+p+p):
        diag[n,:-1] = diag[n-1,1:] + S[n,:-1] * 1
    for h,w in itertools.product(range(p,H+p),range(p,W+p)):
        n = min(h-p,w-p)
        L = S[h,w-1:w-n-1:-1]
        U = S[h-1:h-n-1:-1,w]
        RD = diag[h+1:h+n+1,w] - diag[h,w+1:w+n+1]
        cnt += (L*U*RD).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
  h, w = map(int, input().split())
  s = [input().strip() for _ in range(h)]
  ld = [[0 for _ in range(2*(h+w)+w+2)] for _ in range(2*(h+w)+h+2)]  # 左上から累積
  rd = [[0 for _ in range(2*(h+w)+w+2)] for _ in range(2*(h+w)+h+2)]  # 右上から累積
  for i in range(1, 2*(h+w)+h+1):
    for j in range(1, 2*(h+w)+w+1):
      ld[i][j] += ld[i-1][j-1] + (1 if h+w <= i < h+w+h and h+w <= j < h+w+w and s[i-h-w][j-h-w] == '#' else 0)
      rd[i][j] += rd[i-1][j+1] + (1 if h+w <= i < h+w+h and h+w <= j < h+w+w and s[i-h-w][j-h-w] == '#' else 0)

  ans = 0
  for i in range(h):
    i += h+w
    for j in range(w):
      j += h+w
      for l in range(1, h + w):
        up = 1 if i - l - h - w >= 0 and s[i-h-w-l][j-h-w] == '#' else 0
        down = 1 if i + l - w - h < h and s[i-h-w+l][j-h-w] == '#' else 0
        left = 1 if j - l - h - w >= 0 and s[i-h-w][j-h-w-l] == '#' else 0
        right = 1 if j + l - w - h < w and s[i-h-w][j+l-h-w] == '#' else 0
        up_left = rd[i][j-l] - rd[i-l][j] - left
        up_right = ld[i][j+l] - ld[i-l][j] - right
        down_left = ld[i+l][j] - ld[i][j-l] - down
        down_right = rd[i+l][j] - rd[i][j+l] - down
        ans += up*left*down + up*right*down + left*up*right + left*down*right + \
          up*right*down_left + up*left*down_right + down*right*up_left + down*left*up_right
  print(ans)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


h,w = inm()
s = [ [] for i in range(h) ]
for i in range(h):
    ss = input()
    s[i] = [1 if ss[j]=='#' else 0 for j in range(w)]

b = [ [0]*(w+h+2) for j in range(w+h+2) ]
#cnt = 1
for i in range(h):
    for j in range(w):
        b[i-j][i+j] = s[i][j]


accz = [ [0]*(w+h+2) for j in range(w+h+2) ]
accu = [ [0]*(w+h+2) for j in range(w+h+2) ]
for z in range(-w,h):
    for u in range(w+h-1):
        accz[z][u] = accz[z-1][u] + b[z][u]
        accu[z][u] = accu[z][u-1] + b[z][u]


sum = 0
for u in range(w+h):
    lft = -u if u<w else u-2*w+2
    rgt =  u if u<h else 2*h-u-2
    zs = [ z for z in range(lft,rgt+1) if b[z][u] == 1 ]
    sz = len(zs)
    for i in range(sz-1):
        for j in range(i+1,sz):
            z = zs[i]
            zz = zs[j]
            uu = u - (zz-z)
            if uu>=0:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump
            uu = u + (zz-z)
            if uu<=w+h:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump

for z in range(-w+1,h):
    lo = abs(z)
    hi =  2*w+z-2 if z<h-w else 2*h-z-2
    for u in range(lo, hi+1):
        if b[z][u]==0:
            continue
        for uu in range(u+2,hi+1):
            if b[z][uu]==0:
                continue
            zz = z - (uu-u)
            if zz >= 1-w:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

            zz = z + (uu-u)
            if zz <= h-1:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


h,w = inm()
s = [ [] for i in range(h) ]
for i in range(h):
    ss = input()
    s[i] = [1 if ss[j]=='#' else 0 for j in range(w)]

b = [ [0]*(w+h+2) for j in range(w+h+2) ]
#cnt = 1
for i in range(h):
    for j in range(w):
        b[i-j][i+j] = s[i][j]


accz = [ [0]*(w+h+2) for j in range(w+h+2) ]
accu = [ [0]*(w+h+2) for j in range(w+h+2) ]
for z in range(-w,h):
    for u in range(w+h-1):
        accz[z][u] = accz[z-1][u] + b[z][u]
        accu[z][u] = accu[z][u-1] + b[z][u]


sum = 0
for u in range(w+h):
    lft = -u if u<w else u-2*w+2
    rgt =  u if u<h else 2*h-u-2
    zs = [ z for z in range(lft,rgt+1) if b[z][u] == 1 ]
    for p in itertools.combinations(zs,2):
            z = min(p)
            zz = max(p)
            uu = u - (zz-z)
            if uu>=0:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump
            uu = u + (zz-z)
            if uu<=w+h:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump

for z in range(-w+1,h):
    lo = abs(z)
    hi =  2*w+z-2 if z<h-w else 2*h-z-2
    for u in range(lo, hi+1):
        if b[z][u]==0:
            continue
        for uu in range(u+2,hi+1):
            if b[z][uu]==0:
                continue
            zz = z - (uu-u)
            if zz >= 1-w:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

            zz = z + (uu-u)
            if zz <= h-1:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


h,w = inm()
s = [ [] for i in range(h) ]
for i in range(h):
    ss = input()
    s[i] = [1 if ss[j]=='#' else 0 for j in range(w)]

b = np.ndarray(shape=(w+h+2,w+h+2), dtype=int)
accz = np.ndarray(shape=(w+h+2,w+h+2), dtype=int)
accu = np.ndarray(shape=(w+h+2,w+h+2), dtype=int)
for i in range(w+h+2):
    for j in range(w+h+2):
        b[i][j] = accz[i][j] = accu[i][j] = 0
#b = [ [0]*(w+h+2) for j in range(w+h+2) ]
#cnt = 1
for i in range(h):
    for j in range(w):
        b[i-j][i+j] = s[i][j]


#accz = [ [0]*(w+h+2) for j in range(w+h+2) ]
#accu = [ [0]*(w+h+2) for j in range(w+h+2) ]
for z in range(-w,h):
    for u in range(w+h-1):
        accz[z][u] = accz[z-1][u] + b[z][u]
        accu[z][u] = accu[z][u-1] + b[z][u]


sum = 0
for u in range(w+h):
    lft = -u if u<w else u-2*w+2
    rgt =  u if u<h else 2*h-u-2
    for z in range(lft, rgt+1):
        if b[z][u]==0:
            continue
        for zz in range(z+1,rgt+1):
            if b[zz][u]==0:
                continue
            uu = u - (zz-z)
            if uu>=0:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump
            uu = u + (zz-z)
            if uu<=w+h:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump

for z in range(-w+1,h):
    lo = abs(z)
    hi =  2*w+z-2 if z<h-w else 2*h-z-2
    for u in range(lo, hi+1):
        if b[z][u]==0:
            continue
        for uu in range(u+2,hi+1):
            if b[z][uu]==0:
                continue
            zz = z - (uu-u)
            if zz >= 1-w:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

            zz = z + (uu-u)
            if zz <= h-1:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

print(sum)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


h,w = inm()
s = [ [] for i in range(h) ]
for i in range(h):
    ss = input()
    s[i] = [1 if ss[j]=='#' else 0 for j in range(w)]

b = [ [0]*(w+h+2) for j in range(w+h+2) ]
#cnt = 1
for i in range(h):
    for j in range(w):
        b[i-j][i+j] = s[i][j]


accz = [ [0]*(w+h+2) for j in range(w+h+2) ]
accu = [ [0]*(w+h+2) for j in range(w+h+2) ]
for z in range(-w,h):
    for u in range(w+h-1):
        accz[z][u] = accz[z-1][u] + b[z][u]
        accu[z][u] = accu[z][u-1] + b[z][u]


sum = 0
for u in range(w+h):
    lft = -u if u<w else u-2*w+2
    rgt =  u if u<h else 2*h-u-2
    for z in range(lft, rgt+1):
        if b[z][u]==0:
            continue
        for zz in range(z+1,rgt+1):
            if b[zz][u]==0:
                continue
            uu = u - (zz-z)
            if uu>=0:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump
            uu = u + (zz-z)
            if uu<=w+h:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump

for z in range(-w+1,h):
    lo = abs(z)
    hi =  2*w+z-2 if z<h-w else 2*h-z-2
    for u in range(lo, hi+1):
        if b[z][u]==0:
            continue
        for uu in range(u+2,hi+1):
            if b[z][uu]==0:
                continue
            zz = z - (uu-u)
            if zz >= 1-w:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

            zz = z + (uu-u)
            if zz <= h-1:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

print(sum)

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)


h,w = inm()
s = [ [] for i in range(h) ]
for i in range(h):
    ss = input()
    s[i] = [1 if ss[j]=='#' else 0 for j in range(w)]

b = [ [0]*(w+h+2) for j in range(w+h+2) ]
#cnt = 1
for i in range(h):
    for j in range(w):
        b[i-j][i+j] = s[i][j]
        #if s[i][j] > 0:
        #  b[i-j][i+j] = cnt
        #  cnt += 1
        ddprint("b {} {} frm s {} {}: {}".format( \
            i-j,i+j,i,j,s[i][j]))

ddprint("s")
for i in range(h):
  ddprint(s[i])
ddprint("b")
for i in range(w+h+2):
  if DBG:
    printn("{}: ".format(i))
  ddprint(b[i])

accz = [ [0]*(w+h+2) for j in range(w+h+2) ]
accu = [ [0]*(w+h+2) for j in range(w+h+2) ]
for z in range(-w,h):
    for u in range(w+h-1):
        accz[z][u] = accz[z-1][u] + b[z][u]
        accu[z][u] = accu[z][u-1] + b[z][u]

ddprint("accz")
for i in range(w+h+2):
  ddprint(accz[i])
ddprint("accu")
for i in range(w+h+2):
  ddprint(accu[i])

sum = 0
for u in range(w+h):
    lft = -u if u<w else u-2*w+2
    rgt =  u if u<h else 2*h-u-2
    for z in range(lft, rgt+1):
        if b[z][u]==0:
            continue
        for zz in range(z+1,rgt+1):
            if b[zz][u]==0:
                continue
            uu = u - (zz-z)
            if uu>=0:   # 単にzz..zでよいか？-右側はNG
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump
            uu = u + (zz-z)
            if uu<=w+h:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                sum += sump

for z in range(-w+1,h):
    lo = abs(z)
    hi =  2*w+z-2 if z<h-w else 2*h-z-2
    for u in range(lo, hi+1):
        if b[z][u]==0:
            continue
        for uu in range(u+2,hi+1):
            if b[z][uu]==0:
                continue
            zz = z - (uu-u)
            if zz >= 1-w:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

            zz = z + (uu-u)
            if zz <= h-1:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                sum += sump

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

def dxprint(x1,y1,x2,y2,x3,y3):
  if DBG:
    a = [(x1,y1),(x2,y2),(x3,y3)]
    a.sort()
    print("@<({},{}) ({},{}) ({},{})>".format( \
      a[0][0],a[0][1], a[1][0],a[1][1], a[2][0],a[2][1]))

def dmprint(z1,u1,z2,u2,z3,u3):
  if DBG:
    x1 = (z1+u1)//2
    y1 = (u1-z1)//2
    x2 = (z2+u2)//2
    y2 = (u2-z2)//2
    x3 = (z3+u3)//2
    y3 = (u3-z3)//2
    dxprint(x1,y1,x2,y2,x3,y3)

def pzprint(n,z,zz,u,uu,sump,z3,z4,l2,r2):
    s1 = "{}) z {} zz {} u {} uu {} sump {}".format( \
                    n,z,zz,u,uu,sump)
    s2 = "  z3 {} z4 {} l2 {} r2 {}".format( \
                    z3,z4,l2,r2)
    s3 = " p1 {},{} p2 {},{}".format( \
            (z+u)//2, (u-z)//2, (zz+u)//2, (u-zz)//2)
    s4 = " p3 {},{} p4 {},{}".format( \
      (z3+uu)//2, (uu-z3)//2, (z4+1+uu)//2, (uu-z4-1)//2 )
    ddprint(s1)
    ddprint(s2)
    ddprint(s3)
    ddprint(s4)

def puprint(n,z,zz,u,uu,sump,u3,u4,l2,h2):
    s1 = "{}) z {} zz {} u {} uu {} sump {}".format( \
                    n,z,zz,u,uu,sump)
    s2 = "  u3 {} u4 {} l2 {} h2 {}".format( \
                    u3,u4,l2,h2)
    s3 = " p1 {},{} p2 {},{}".format( \
            (z+u)//2, (u-z)//2, (z+uu)//2, (uu-z)//2)
    s4 = " p3 {},{} p4 {},{}".format( \
      (zz+u3)//2, (u3-zz)//2, (zz+u4+1)//2, (u4+1-zz)//2 )
    ddprint(s1)
    ddprint(s2)
    ddprint(s3)
    ddprint(s4)


h,w = inm()
s = [ [] for i in range(h) ]
for i in range(h):
    ss = input()
    s[i] = [1 if ss[j]=='#' else 0 for j in range(w)]

b = [ [0]*(w+h+2) for j in range(w+h+2) ]
#cnt = 1
for i in range(h):
    for j in range(w):
        b[i-j][i+j] = s[i][j]
        #if s[i][j] > 0:
        #  b[i-j][i+j] = cnt
        #  cnt += 1
        ddprint("b {} {} frm s {} {}: {}".format( \
            i-j,i+j,i,j,s[i][j]))

ddprint("s")
for i in range(h):
  ddprint(s[i])
ddprint("b")
for i in range(w+h+2):
  if DBG:
    printn("{}: ".format(i))
  ddprint(b[i])

accz = [ [0]*(w+h+2) for j in range(w+h+2) ]
accu = [ [0]*(w+h+2) for j in range(w+h+2) ]
for z in range(-w,h):
    for u in range(w+h-1):
        accz[z][u] = accz[z-1][u] + b[z][u]
        accu[z][u] = accu[z][u-1] + b[z][u]

ddprint("accz")
for i in range(w+h+2):
  ddprint(accz[i])
ddprint("accu")
for i in range(w+h+2):
  ddprint(accu[i])

sum = 0
for u in range(w+h):
    lft = -u if u<w else u-2*w+2
    rgt =  u if u<h else 2*h-u-2
    for z in range(lft, rgt+1):
        if b[z][u]==0:
            continue
        for zz in range(z+1,rgt+1):
            if b[zz][u]==0:
                continue
            uu = u - (zz-z)
            if uu>=0:   # 単にzz..zでよいか？-右側はNG
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                # # # #
                cnt = 0
                for i in range(z3,z4,-1):
                    if b[i][uu]==1:
                        dmprint(z,u,zz,u,i,uu)
                        cnt += 1
                if cnt != sump:
                    ddprint("cnt mismch!")
                # # # #
                sum += sump
                if sump!=0:
                  pzprint( \
                    1,z,zz,u,uu,sump,z3,z4,lft2,rgt2)
            uu = u + (zz-z)
            if uu<=w+h:
                lft2 = -uu if uu<w else uu-2*w+2
                rgt2 =  uu if uu<h else 2*h-uu-2
                z3 = min(zz,rgt2)
                z4 = max(z,lft2)-1
                sump = accz[z3][uu] - accz[z4][uu]
                # # # #
                cnt = 0
                for i in range(z3,z4,-1):
                    if b[i][uu]==1:
                        dmprint(z,u,zz,u,i,uu)
                        cnt += 1
                if cnt != sump:
                    ddprint("cnt mismch!")
                # # # #
                sum += sump
                if sump!=0:
                  pzprint( \
                    2,z,zz,u,uu,sump,z3,z4,lft2,rgt2)

for z in range(-w+1,h):
    lo = abs(z)
    hi =  2*w+z-2 if z<h-w else 2*h-z-2
    for u in range(lo, hi+1):
        if b[z][u]==0:
            continue
        for uu in range(u+2,hi+1):
            if b[z][uu]==0:
                continue
            zz = z - (uu-u)
            if zz >= 1-w:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                # # # #
                cnt = 0
                for i in range(u3,u4,-1):
                    if b[zz][i]==1:
                        dmprint(z,u,z,uu,zz,i)
                        cnt += 1
                if cnt != sump:
                    ddprint("cnt mismch!")
                # # # #
                sum += sump
                if sump!=0:
                    puprint( \
                      3,z,zz,u,uu,sump,u3,u4,lo2,hi2)

            zz = z + (uu-u)
            if zz <= h-1:
                lo2 = abs(zz)
                hi2 =  2*w+zz-2 if zz<h-w else 2*h-zz-2
                u3 = min(uu-1,hi2)
                u4 = max(u+1,lo2)-1
                sump = accu[zz][u3] - accu[zz][u4]
                # # # #
                cnt = 0
                for i in range(u3,u4,-1):
                    if b[zz][i]==1:
                        dmprint(z,u,z,uu,zz,i)
                        cnt += 1
                if cnt != sump:
                    ddprint("cnt mismch!")
                # # # #
                sum += sump
                if sump!=0:
                    puprint( \
                      4,z,zz,u,uu,sump,u3,u4,lo2,hi2)

print(sum)

Submission status: Time Limit Exceeded

Solution code:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    
     
H, W = getIntList()
#print(N)
zs = []
for i in range(H):
    s = input()
    zs .append(s)

def iscoin( p0, p1):
    x = p0[0] + p1[0]
    if x<0 or x>= H: return False
    y = p0[1] + p1[1]
    if y<0 or y>= W: return False
    if zs[x][y] =='.': return False
    return True

res = 0
for i in range(2, 2*(H+W) //3+2, 2):
    za = []
    for a  in range(i+1):
        b = i - a
        za.append( (a,b) )
        #if a:
         #   za.append( (-a,b) )
        if a and b:
            za.append( (a,-b) )
            #if a:
             #   za.append( (-a,-b) )
    za.sort()
    nza = len(za)
    zt = []
    for i0 in range(nza):
        for i1 in range(i0+1, nza) :
            x0= za[i0]
            x1 = za[i1]
            d = abs(x0[0] - x1[0]) + abs(x0[1] - x1[1])
            if d== i:
                zt.append( (x0,x1) )
    #print(zt)
    for x in range(H):
        for y in range(W):
            if zs[x][y] =='.': continue
            for a,b  in zt:
                if not iscoin( (x,y), a ): continue
                if not iscoin( (x,y), b) : continue
                res +=1                

print(res )

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
(H,W) = map(int,input().split())
field = -np.ones((H,W),dtype=np.int)
points = []
i = 0
for h in range(H):
    line = input()
    for w in range(W):
        if line[w] == '#':
            points.append((h,w))
            field[h,w] = i
            i = i+1

points = np.array(points)
N = len(points)

answer = 0
for m in range(N):
    for n in range(m,N):
        p1 = points[m]
        p2 = points[n]
        (dy, dx) = p2 - p1
        distance = np.abs([dy,dx]).sum()
        if distance % 2:
            continue

        if dx < 0:
            dx = -dx
            s = -1
        else:
            s = 1
        
        if dx > dy:
            p3s = np.array([ p1 + [ (dx+3*dy)//2, s*(dx-dy)//2 ]])
        elif dx < dy:
            p3s = np.array([ p1 + [ (-dx+dy)//2, s*(3*dx+dy)//2 ]])
        else: # dx == dy
            p3s = np.array([ p1 + [ dx + u, s*(-dx + u) ] for u in range(dx+1) ])

        for p in p3s:
            if (0<=p[0]<H) and (0<=p[1]<W) and (field[p[0],p[1]]>n):
                answer = answer + 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
H, W = [int(i) for i in input().split(' ')]

cross = [[0] * (H + W -1) for _ in range(H + W - 1)]
for i, line in enumerate(sys.stdin):
    for j, c in enumerate(line.strip()):
        if c == "#":
            cross[i+j][i-j+W-1] = 1

across = [[0] + list(itertools.accumulate(xs)) for xs in cross]
r_cross = [[xs[i] for xs in cross] for i in range(H + W - 1)]
across2 = [[0] + list(itertools.accumulate(xs)) for xs in r_cross]

r = 0
for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[i][j] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[i][k] == 1:
                if i - (k-j) >= 0:
                    r += across[i - (k - j)][k+1] - across[i - (k - j)][j]
                if i + (k-j) < H + W - 1:
                    r += across[i + (k - j)][k+1] - across[i + (k - j)][j]

for i in range(H+W-1):
    for j in range(H+W-1):
        if cross[j][i] != 1:
            continue
        for k in range(j+1, H+W-1):
            if cross[k][i] == 1:
                if i - (k-j) >= 0:
                    r += across2[i - (k - j)][k] - across2[i - (k - j)][j+1]
                if i + (k-j) < H + W - 1:
                    r += across2[i + (k - j)][k] - across2[i + (k - j)][j+1]

print(r)

Submission status: Time Limit Exceeded

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

"""
tenka1-2018 E
"""

from itertools import product
from itertools import combinations

h, w = map(int, input().split())
slili = [list(input()) for i in range(h)]

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '#':
        coinsetli[i+j+1].add(j-i)

jmin = -304
jmin2 = jmin+2


coinacumdictli = [[] for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(jmin+tt, 303, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i].append(tmp)


coinacumdictli2 = [[] for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(len(coinacumdictli[i])-1):
        coinacumdictli2[i].append(coinacumdictli[i][j]+coinacumdictli[i][j+1])


coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
    tt = (i % 2) - 1

    def rescale(x):
        return (x-jmin2-tt)//2
    coinlili[i] = sorted(list(map(rescale, coinsetli[i])))


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinlili[i], 2):
        j = 2*(y-x)
        imj = i-j
        ipj = i+j
        if imj >= 1:
            ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
        if ipj <= h+w-1:
            ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]

# repeat after reversing along the vertical axis
for i in range(h):
    slili[i].reverse()

coinsetli = [set() for i in range(h+w)]
for i, j in product(range(h), range(w)):
    if slili[i][j] == '#':
        coinsetli[i+j+1].add(j-i)

jmin = -304
jmin2 = jmin+2

coinacumdictli = [[] for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(jmin+tt, 303, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i].append(tmp)


coinacumdictli2 = [[] for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(len(coinacumdictli[i])-1):
        coinacumdictli2[i].append(coinacumdictli[i][j]+coinacumdictli[i][j+1])

coinlili = [[] for i in range(len(coinsetli))]
for i in range(len(coinsetli)):
    tt = (i % 2) - 1

    def rescale(x):
        return (x-jmin2-tt)//2
    coinlili[i] = sorted(list(map(rescale, coinsetli[i])))


for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinlili[i], 2):
        j = 2*(y-x)
        imj = i-j
        ipj = i+j
        if imj >= 1:
            ansdouble += coinacumdictli2[imj][y] - coinacumdictli2[imj][x]
        if ipj <= h+w-1:
            ansdouble += coinacumdictli2[ipj][y] - coinacumdictli2[ipj][x]

print(ansdouble//2)