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

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

class CumulativeSum2D:
    def __init__(self, field):
        self.h = len(field)
        self.w = len(field[0])
        self.h_offset = self.h
        self.w_offset = self.w
        self.field = field
        self.cumsum = [[0] * (self.w + self.w_offset * 2) for _ in range(self.h_offset)]
        for line in self.field:
            self.cumsum.append([0] * self.w_offset + line + [0] * self.w_offset)
        for i in range(self.h_offset):
            self.cumsum.append([0] * (self.w + self.w_offset * 2))
    
    def calc_horizontal_cumsum(self):
        # Calc horizontal cumlative sum
        for i in range(self.h_offset, self.h_offset + self.h):
            for j in range(self.w_offset, self.w_offset + self.w):
                self.cumsum[i][j] += self.cumsum[i][j-1]
        # Calc vertical cumlative sum
        for i in range(self.w_offset, self.w_offset + self.w):
            for j in range(self.h_offset, self.h_offset + self.h):
                self.cumsum[j][i] += self.cumsum[j-1][i]

    def calc_diagonal_cumsum(self):
        # Calc ul to dr
        for h in range(self.h_offset, self.h_offset + self.h):
            delta = 1
            while delta + h < self.h_offset * 2 + self.h and self.w_offset + delta < self.w_offset * 2 + self.w:
                self.cumsum[h + delta][self.w_offset + delta] += self.cumsum[h + delta-1][self.w_offset + delta-1]
                delta += 1
        for w in range(self.w_offset + 1, self.w_offset + self.w):
            delta = 1
            while delta + w < self.w_offset * 2 + self.w and self.h_offset + delta < self.h_offset * 2 + self.h:
                self.cumsum[self.h_offset + delta][w + delta] += self.cumsum[self.h_offset + delta - 1][w + delta - 1]
                delta += 1
        # Calc ur to dl
        for h in range(self.h_offset * 2 + self.h - 1, - 1, -1):
            delta = 1
            while delta + h < self.h_offset * 2 + self.h and self.w_offset * 2 + self.w - 1 - delta >= 0:
                self.cumsum[h + delta][self.w_offset * 2 + self.w - 1 - delta] += self.cumsum[h + delta - 1][self.w_offset * 2 + self.w - 1 - delta + 1]
                delta += 1
        for w in range(self.w_offset * 2 + self.w - 2, -1, -1):
            delta = 1
            while w - delta >= 0 and delta < self.h_offset * 2 + self.h:
                self.cumsum[delta][w - delta] += self.cumsum[delta - 1][w - delta + 1]
                delta += 1
    
    # Get horizontal sum in l <= x < r, u <= y < d
    # x: right, y: down
    def get_horizontal_sum(self, x1, y1, x2, y2):
        ret = self.cumsum[y2-1 + self.h_offset][x2-1 + self.w_offset]
        ret -= self.cumsum[y2-1 + self.h_offset][x1-1 + self.w_offset]
        ret -= self.cumsum[y1-1 + self.h_offset][x2-1 + self.w_offset]
        ret += self.cumsum[y1-1 + self.h_offset][x1-1 + self.w_offset]
        return ret
    
    # Get horizontal sum in x1 <= x <= x2, y1 <= y <= y2 
    def get_diagonal_sum(self, x1, y1, x2, y2):
        if ((x1 + y1) - (x2 + y2)) % 2 == 1:
            return None
        u2 = x2 + y2 
        v2 = x2 - y2
        u1 = x1 + (y1 - 2)
        v1 = x1 - (y1 - 2)
        x3 = (u2 + v1) // 2
        y3 = (u2 - v1) // 2
        x4 = (u1 + v2) // 2
        y4 = (u1 - v2) // 2
        ret = self.cumsum[y2 + self.h_offset][x2 + self.w_offset]
        ret -= self.cumsum[y3 + self.h_offset][x3 + self.w_offset]
        ret -= self.cumsum[y4 + self.h_offset][x4 + self.w_offset]
        ret += self.cumsum[y1-2 + self.h_offset][x1 + self.w_offset]
        return ret
        

    def print(self):
        print("h:", self.h, "w:", self.w)
        for i in range(self.h_offset, self.h_offset + self.h):
            print(self.cumsum[i][self.w_offset:self.w_offset + self.w])

if __name__ == "__main__":
    n, m = [int(item) for item in input().split()]
    field_lu = [[0] * m for _ in range(n)]
    field_ru = [[0] * n for _ in range(m)]
    for i in range(n):
        line = input().rstrip()
        for j in range(m):
            if line[j] == "#":
                field_lu[i][j] = 1
                field_ru[m-1-j][i] = 1

    cs_lu = CumulativeSum2D(field_lu)
    cs_lu.calc_diagonal_cumsum()

    lu_to_rd = [[] for _ in range(n + m - 1)]
    for i in range(m):
        x = i; y = 0
        delta = 0
        while x + delta < m and y + delta < n: 
            if field_lu[y + delta][x + delta] == 1:
                lu_to_rd[i].append((x + delta, y + delta))
            delta += 1
    for i in range(1, n):
        x = 0; y = i
        delta = 0
        while x + delta < m and y + delta < n:
            if field_lu[y + delta][x + delta] == 1:
                lu_to_rd[i + m - 1].append((x + delta, y + delta))
            delta += 1

    ans = 0
    double = 0
    for line in lu_to_rd:
        length = len(line)
        if length <= 1:
            continue
        for i in range(length):
            for j in range(i+1, length):
                x1 = line[i][0]
                y1 = line[i][1]
                x2 = line[j][0]
                y2 = line[j][1]
                d = abs(x1 - x2)
                # Proc upper
                x3 = x1 + d
                y3 = y1 - d
                x4 = x2 + d
                y4 = y2 - d
                if 0 <= x3 < m and 0 <= y3 < n and field_lu[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < m and 0 <= y4 < n and field_lu[y4][x4] == 1:
                    double += 1
                ans += cs_lu.get_diagonal_sum(x3, y3, x4, y4)
                # Proc lower
                x3 = x1 - d
                y3 = y1 + d
                x4 = x2 - d
                y4 = y2 + d
                if 0 <= x3 < m and 0 <= y3 < n and field_lu[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < m and 0 <= y4 < n and field_lu[y4][x4] == 1:
                    double += 1
                ans += cs_lu.get_diagonal_sum(x3, y3, x4, y4)

    cs_ru = CumulativeSum2D(field_ru)
    cs_ru.calc_diagonal_cumsum()
    lu_to_rd = [[] for _ in range(n + m - 1)]
    for i in range(n):
        x = i; y = 0
        delta = 0
        while x + delta < n and y + delta < m: 
            if field_ru[y + delta][x + delta] == 1:
                lu_to_rd[i].append((x + delta, y + delta))
            delta += 1
    for i in range(1, m):
        x = 0; y = i
        delta = 0
        while x + delta < n and y + delta < m:
            if field_ru[y + delta][x + delta] == 1:
                lu_to_rd[i + n - 1].append((x + delta, y + delta))
            delta += 1
    for line in lu_to_rd:
        length = len(line)
        if length <= 1:
            continue
        for i in range(length):
            for j in range(i+1, length):
                x1 = line[i][0]
                y1 = line[i][1]
                x2 = line[j][0]
                y2 = line[j][1]
                d = abs(x1 - x2)
                # Proc upper
                x3 = x1 + d
                y3 = y1 - d
                x4 = x2 + d
                y4 = y2 - d
                if 0 <= x3 < n and 0 <= y3 < m and field_ru[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < n and 0 <= y4 < m and field_ru[y4][x4] == 1:
                    double += 1
                ans += cs_ru.get_diagonal_sum(x3, y3, x4, y4)
                # Proc lower
                x3 = x1 - d
                y3 = y1 + d
                x4 = x2 - d
                y4 = y2 + d
                if 0 <= x3 < n and 0 <= y3 < m and field_ru[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < n and 0 <= y4 < m and field_ru[y4][x4] == 1:
                    double += 1
                ans += cs_ru.get_diagonal_sum(x3, y3, x4, y4)

    print(ans - double // 2)

Submission status: Wrong Answer

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(1,H),range(1,W)):
        n = h if h<w else w
        cnt += (S[h,w-1::-1][:n]*S[h-1::-1,w][:n]*(diag[h+1:h+n+1,w]-diag[h,w+1:w+n+1])).sum()
    return cnt

x = []
x.append(F(S,H,W))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 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+2):
    for u in range(w+h+2):
        accz[z-h][u] = accz[z-1-h][u] + b[z-h][u]
        accu[z-h][u] = accu[z-h][u-1] + b[z-h][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
                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]
                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 >= -h:
                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
                if sump!=0:
                    puprint( \
                      3,z,zz,u,uu,sump,u3,u4,lo2,hi2)

            zz = z + (uu-u)
            if zz <= 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
                if sump!=0:
                    puprint( \
                      4,z,zz,u,uu,sump,u3,u4,lo2,hi2)

print(sum)

Submission status: Wrong Answer

Solution code:





def distance(a,b):
	return abs(a[0]-b[0])+abs(a[1]-b[1])


n=0

H,W=input().split()
H=int(H)
W=int(W)
r=[]
for i in range(H):
	r.append(input().split())
stones=[]
print(r)
for i in range(H):
	for j in range(W):
		if(r[i][0][j]=="#"):
			stones.append([j,i])

for i in range(len(stones)):
	for j in range(i+1,len(stones)):
		d=distance(stones[i],stones[j])
		for k in range(j+1,len(stones)):
			if(distance(stones[i],stones[k])==distance(stones[j],stones[k])==d):
				n+=1
				print(stones[i],stones[j],stones[k])
print(n)

Submission status: Wrong Answer

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]

print(r)

Submission status: Wrong Answer

Solution code:
# E
H, W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(list(input()))

res = 0
# cross
cross_posi = [[0]*(H+W-1) for _ in range(H+W-1)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            cross_posi[i+j][i-j+W-1] = 1
            
# pre-compute
cross_posi_1 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[i][j]
        cross_posi_1[i][j+1] = r
        
cross_posi_2 = [[0]*(H+W) for _ in range(H+W-1)]
for i in range(H+W-1):
    r = 0
    for j in range(H+W-1):
        r += cross_posi[j][i]
        cross_posi_2[i][j+1] = r

for s in range(H+W-1):
    for t in range(s%2, H+W-2, 2):
        if cross_posi[s][t] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[s][u] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_1[s-d][u+1] - cross_posi_1[s-d][t]
                    if s+d < H+W-1:
                        res += cross_posi_1[s+d][u+1] - cross_posi_1[s+d][t]
for s in range(H+W-1):
    for t in range(s%2, H+W-2, 2):
        if cross_posi[t][s] == 1:
            for u in range(t+2, H+W-1, 2):
                if cross_posi[u][s] == 1:
                    d = (u - t)
                    if s >= d:
                        res += cross_posi_2[s-d][u] - cross_posi_2[s-d][t+1]
                    if s+d < H+W-1:
                        res += cross_posi_2[s+d][u] - cross_posi_2[s+d][t+1]
print(res)

Submission status: Wrong Answer

Solution code:
def dist(i1, j1, i2, j2):
    return abs(i1-i2) + abs(j1 - j2)
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
Y = []
for i in range(H):
    for j in range(W):
        if X[i][j]:
            Y.append((i,j))

ans = 0
for i in range(len(Y)-2):
    for j in range(i+1, len(Y)-1):
        for k in range(j+1, len(Y)):
            if dist(Y[i][0], Y[i][1], Y[j][0], Y[j][1]) == dist(Y[i][0], Y[i][1], Y[k][0], Y[k][1]):
                if dist(Y[i][0], Y[i][1], Y[k][0], Y[k][1]) == dist(Y[k][0], Y[k][1], Y[j][0], Y[j][1]):
                    if dist(Y[k][0], Y[k][1], Y[j][0], Y[j][1]) == dist(Y[i][0], Y[i][1], Y[j][0], Y[j][1]):
                        ans += 1

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

h, w = map(int, input().split())
field = [input() for _ in range(h)]

l = max(h, w)
precalc_rd = []
precalc_ld = []
for ij in range(h + w - 1):
    coins = [0] * (l + 1)
    min_i = max(0, ij - w + 1)
    max_i = ij - max(0, ij - h + 1)
    offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
    for d in range(max_i - min_i + 1):
        i = min_i + d
        j = ij - i
        if field[i][j] == '#':
            coins[offset + d] = 1
    precalc_ld.append(list(accumulate(coins)))

for ij in range(-w + 1, h):
    coins = [0] * (l + 1)
    min_i = max(0, ij)
    max_i = ij + min(w - 1, h - ij - 1)
    offset = (min_i + (min_i - ij)) // 2 + 1
    for d in range(max_i - min_i + 1):
        i = min_i + d
        j = i - ij
        if field[i][j] == '#':
            coins[offset + d] = 1
    precalc_rd.append(list(accumulate(coins)))

ans = 0

for ij in range(h + w - 1):
    min_i = max(0, ij - w + 1)
    max_i = ij - max(0, ij - h + 1)
    offset = (min_i - (ij - min_i) + w - 1) // 2 + 1
    for sd in range(max_i - min_i + 1):
        si = min_i + sd
        sj = ij - si
        if field[si][sj] == '.':
            continue
        for td in range(sd + 1, max_i - min_i + 1):
            ti = min_i + td
            tj = ij - ti
            if field[ti][tj] == '.':
                continue
            dij = (td - sd) * 2
            if ij - dij >= 0:
                ans += precalc_ld[ij - dij][offset + td - 1] - precalc_ld[ij - dij][offset + sd - 1]
            if ij + dij <= h + w - 2:
                ans += precalc_ld[ij + dij][offset + td] - precalc_ld[ij + dij][offset + sd]

for ij in range(-w + 1, h):
    min_i = max(0, ij)
    max_i = ij + min(w - 1, h - ij - 1)
    offset = (min_i + (min_i - ij)) // 2 + 1
    for sd in range(max_i - min_i + 1):
        si = min_i + sd
        sj = si - ij
        if field[si][sj] == '.':
            continue
        for td in range(sd + 1, max_i - min_i + 1):
            ti = min_i + td
            tj = ti - ij
            if field[ti][tj] == '.':
                continue
            dij = (td - sd) * 2
            if ij - dij + w - 1 >= 0:
                ans += precalc_rd[ij - dij + w - 1][offset + td] - precalc_rd[ij - dij + w - 1][offset + sd]
            if ij + dij + w - 1 <= h + w - 2:
                ans += precalc_rd[ij + dij + w - 1][offset + td - 1] - precalc_rd[ij + dij + w - 1][offset + sd - 1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
def r(X):
    Y = [[0 for x in range(len(X))] for xx in range(len(X[0]))]
    for i in range(len(X[0])):
        for j in range(len(X)):
            # print(i,j)
            Y[i][j] = X[len(X)-j-1][i]
    return Y
    
    
c = 0
for t in range(4):
    X = r(X)
    for i in range(len(X)):
        for j in range(len(X[0])):
            if X[i][j] > 0:
                for n in range(1, min(i+1, len(X[0])-j)):
                    if i-n >= 0 and i-n < len(X) and j+n >= 0 and j+n < len(X[0]):
                        if X[i-n][j+n] > 0:
                            for m in range(n):
                                if i-n-m >= 0 and i-n-m < len(X) and j-n+m >= 0 and j-n+m < len(X[0]):
                                    if X[i-n-m][j-n+m] > 0:
                                        #print (i,j,n,m, "get1")
                                        c += 1
print (c)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
X = [[[0, 1][a=="#"] for a in input()] for i in range(H)]
def countRD(n, i, j):
    return ccc(n, i, j, 1, 1)
def countRU(n, i, j):
    return ccc(n, i, j, -1, 1)
def countLD(n, i, j):
    return ccc(n, i, j, 1, -1)
def countLU(n, i, j):
    return ccc(n, i, j, -1, -1)
def countR(n, i, j):
    return cc(n, i, j, 0, 1)
def countL(n, i, j):
    return cc(n, i, j, 0, -1)
def countD(n, i, j):
    return cc(n, i, j, 1, 0)
def countU(n, i, j):
    return cc(n, i, j, -1, 0)
def ccc(n, i, j, DU, RL):
    c = 0
    for k in range(1, n):
        if i+k*DU >= 0 and i+k*DU < H:
            if j+(n-k)*RL >= 0 and j+(n-k)*RL < W:
                c += X[i+k*DU][j+(n-k)*RL]
    return c
def cc(n, i, j, DU, RL):
    ret = 0
    if i+n*DU >= 0 and i+n*DU < H:
        if j+n*RL >= 0 and j+n*RL < W:
            ret = X[i+n*DU][j+n*RL]
    return ret

ans = 0
for i in range(H):
    for j in range(W):
        for n in range(1, min(max(i+j,H-i+W-j), max(i+W-j,H-i+j))+2):
            if countR(n, i, j) and countD(n, i, j):
                ans += countLU(n, i, j)
            if countR(n, i, j) and countU(n, i, j):
                ans += countLD(n, i, j)
            if countL(n, i, j) and countD(n, i, j):
                ans += countRU(n, i, j)
            if countL(n, i, j) and countU(n, i, j):
                ans += countRD(n, i, j)
            if countR(n, i, j) and countD(n, i, j) and countL(n, i, j):
                ans += 1
            if countR(n, i, j) and countD(n, i, j) and countU(n, i, j):
                ans += 1
            if countR(n, i, j) and countU(n, i, j) and countL(n, i, j):
                ans += 1
            if countD(n, i, j) and countU(n, i, j) and countL(n, i, j):
                ans += 1
            
            
print (ans)

Submission status: Time Limit Exceeded

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

H, W = map(int, readline().split())
G = [[0]*W for _ in range(H)]
L1 = [[0]*1000 for _ in range(W+H-1)]
geta1 = W-1
L2 = [[0]*1000 for _ in range(W+H-1)]
for i in range(H):
    S = [1 if s == '#' else 0 for s in readline().strip()]
    for j in range(W):
        G[i][j] = S[j]
        if S[j]:
            L1[i-j+geta1][i] = 1
            L2[i+j][i] = 1
for sub in range(W+H-1):
    for i in range(630):
        L1[sub][i] += L1[sub][i-1]
        L2[sub][i] += L2[sub][i-1]

res = 0
for su in range(2*max(H, W)+1):
    for w in range(max(0, su-H+1), min(W, su+1)):
        h = su-w
        if not G[h][w]:
            continue
        for k in range(1, min(h+1, W-w)):
            if not G[h-k][w+k]:
                continue
            idx1 = h+w-2*k
            if 0 <= idx1 < H+W-1:
                res += L2[idx1][h-k-1] - L2[idx1][h-2*k]
            idx2 = h+w+2*k
            if 0 <= idx2 < H+W-1:
                res += L2[idx2][h+k-1] - L2[idx2][h]

for mi in range(1-W, H):
    for w in range(max(0, -mi), min(W, H-mi)):
        h = mi + w
        if not G[h][w]:
            continue
        for k in range(1, min(H-h, W-w)):
            if not G[h+k][w+k]:
                continue
            idx1 = h-w-2*k + geta1
            if 0 <= idx1 < H+W-1:
                res += L1[idx1][h] - L1[idx1][h-k-1]
            idx2 = h-w+2*k + geta1
            if 0 <= idx2 < H+W-1:
                res += L1[idx2][h+2*k] - L1[idx2][h+k-1]

print(res)

Submission status: Time Limit Exceeded

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

class CumulativeSum2D:
    def __init__(self, field):
        self.h = len(field)
        self.w = len(field[0])
        self.h_offset = self.h
        self.w_offset = self.w
        self.field = field
        self.cumsum = [[0] * (self.w + self.w_offset * 2) for _ in range(self.h_offset)]
        for line in self.field:
            self.cumsum.append([0] * self.w_offset + line + [0] * self.w_offset)
        for i in range(self.h_offset):
            self.cumsum.append([0] * (self.w + self.w_offset * 2))
    
    def calc_diagonal_cumsum(self):
        # Calc ul to dr
        for h in range(self.h_offset, self.h_offset + self.h):
            delta = 1
            while delta + h < self.h_offset * 2 + self.h and self.w_offset + delta < self.w_offset * 2 + self.w:
                self.cumsum[h + delta][self.w_offset + delta] += self.cumsum[h + delta-1][self.w_offset + delta-1]
                delta += 1
        for w in range(self.w_offset + 1, self.w_offset + self.w):
            delta = 1
            while delta + w < self.w_offset * 2 + self.w and self.h_offset + delta < self.h_offset * 2 + self.h:
                self.cumsum[self.h_offset + delta][w + delta] += self.cumsum[self.h_offset + delta - 1][w + delta - 1]
                delta += 1
    
    def get_diagonal_sum(self, x1, y1, x2, y2):
        ret = self.cumsum[y2 + self.h_offset][x2 + self.w_offset]
        ret -= self.cumsum[y1 - 1 + self.h_offset][x1 - 1 + self.w_offset]
        return ret

if __name__ == "__main__":
    n, m = [int(item) for item in input().split()]
    field_lu = [[0] * m for _ in range(n)]
    field_ru = [[0] * n for _ in range(m)]
    for i in range(n):
        line = input().rstrip()
        for j in range(m):
            if line[j] == "#":
                field_lu[i][j] = 1
                field_ru[m-1-j][i] = 1

    cs_lu = CumulativeSum2D(field_lu)
    cs_lu.calc_diagonal_cumsum()

    lu_to_rd = [[] for _ in range(n + m - 1)]
    for i in range(m):
        x = i; y = 0
        delta = 0
        while x + delta < m and y + delta < n: 
            if field_lu[y + delta][x + delta] == 1:
                lu_to_rd[i].append((x + delta, y + delta))
            delta += 1
    for i in range(1, n):
        x = 0; y = i
        delta = 0
        while x + delta < m and y + delta < n:
            if field_lu[y + delta][x + delta] == 1:
                lu_to_rd[i + m - 1].append((x + delta, y + delta))
            delta += 1

    ans = 0
    double = 0
    for line in lu_to_rd:
        length = len(line)
        if length <= 1:
            continue
        for i in range(length):
            for j in range(i+1, length):
                x1, y1 = line[i]
                x2, y2 = line[j]
                d = abs(x1 - x2)
                # Proc upper
                x3 = x1 + d
                y3 = y1 - d
                x4 = x2 + d
                y4 = y2 - d
                if 0 <= x3 < m and 0 <= y3 < n and field_lu[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < m and 0 <= y4 < n and field_lu[y4][x4] == 1:
                    double += 1
                ans += cs_lu.get_diagonal_sum(x3, y3, x4, y4)
                # Proc lower
                x3 = x1 - d
                y3 = y1 + d
                x4 = x2 - d
                y4 = y2 + d
                if 0 <= x3 < m and 0 <= y3 < n and field_lu[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < m and 0 <= y4 < n and field_lu[y4][x4] == 1:
                    double += 1
                ans += cs_lu.get_diagonal_sum(x3, y3, x4, y4)

    cs_ru = CumulativeSum2D(field_ru)
    cs_ru.calc_diagonal_cumsum()
    lu_to_rd = [[] for _ in range(n + m - 1)]
    for i in range(n):
        x = i; y = 0
        delta = 0
        while x + delta < n and y + delta < m: 
            if field_ru[y + delta][x + delta] == 1:
                lu_to_rd[i].append((x + delta, y + delta))
            delta += 1
    for i in range(1, m):
        x = 0; y = i
        delta = 0
        while x + delta < n and y + delta < m:
            if field_ru[y + delta][x + delta] == 1:
                lu_to_rd[i + n - 1].append((x + delta, y + delta))
            delta += 1
    for line in lu_to_rd:
        length = len(line)
        if length <= 1:
            continue
        for i in range(length):
            for j in range(i+1, length):
                x1, y1 = line[i]
                x2, y2 = line[j]
                d = abs(x1 - x2)
                # Proc upper
                x3 = x1 + d
                y3 = y1 - d
                x4 = x2 + d
                y4 = y2 - d
                if 0 <= x3 < n and 0 <= y3 < m and field_ru[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < n and 0 <= y4 < m and field_ru[y4][x4] == 1:
                    double += 1
                ans += cs_ru.get_diagonal_sum(x3, y3, x4, y4)
                # Proc lower
                x3 = x1 - d
                y3 = y1 + d
                x4 = x2 - d
                y4 = y2 + d
                if 0 <= x3 < n and 0 <= y3 < m and field_ru[y3][x3] == 1:
                    double += 1
                if 0 <= x4 < n and 0 <= y4 < m and field_ru[y4][x4] == 1:
                    double += 1
                ans += cs_ru.get_diagonal_sum(x3, y3, x4, y4)

    print(ans - double // 2)