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:
#! /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])


def rescale(x, y, tt):
    return ((min(x, y)-jmin2-tt)//2, (max(x, y)-jmin2-tt)//2)


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = rescale(x, y, tt)
        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])

for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = rescale(x, y, tt)
        j = 2*(y-x)
        imj, ipj = i-j, 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)

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][j] = tmp


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


def rescale(x, y, tt):
    return ((min(x, y)-jmin2-tt)//2, (max(x, y)-jmin2-tt)//2)


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = rescale(x, y, tt)
        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][j] = tmp


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


for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = rescale(x, y, tt)
        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)

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][j] = tmp


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


def rescale(x, y):
    return ((min(x, y)-jmin2-tt)//2, (max(x, y)-jmin2-tt)//2)


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = rescale(x, y)
        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][j] = tmp


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


for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = rescale(x, y)
        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)

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][j] = tmp


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


ansdouble = 0
for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = ((min(x, y)-jmin2-tt)//2, (max(x, y)-jmin2-tt)//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][j] = tmp


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


for i in range(1, h+w):
    tt = (i % 2) - 1
    for x, y in combinations(coinsetli[i], 2):
        x, y = ((min(x, y)-jmin2-tt)//2, (max(x, y)-jmin2-tt)//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)

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)

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(-304+tt, 301, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp


coinacumdictli2 = [{} for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(-302+tt, 301, 2):
        coinacumdictli2[i][j] = coinacumdictli[i][j]+coinacumdictli[i][j-2]


ansdouble = 0
for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        x, y = (min(x, y), max(x, y))
        j = 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)

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(-304+tt, 301, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp


coinacumdictli2 = [{} for i in range(h+w)]
for i in range(1, h+w):
    tt = (i % 2) - 1
    for j in range(-302+tt, 301, 2):
        coinacumdictli2[i][j] = coinacumdictli[i][j]+coinacumdictli[i][j-2]


for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        x, y = (min(x, y), max(x, y))
        j = 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)

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)

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(-300+tt, 301, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp

ansdouble = 0
for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        j = abs(x-y)
        x, y = (min(x, y), max(x, y))
        if i-j >= 1:
            ansdouble += coinacumdictli[i-j][y]+coinacumdictli[i-j][y-2] - coinacumdictli[i-j][x] - coinacumdictli[i-j][x-2]
        if i+j <= h+w-1:
            ansdouble += coinacumdictli[i+j][y]+coinacumdictli[i+j][y-2] - coinacumdictli[i+j][x] - coinacumdictli[i+j][x-2]

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

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    tt = (i % 2) - 1
    for j in range(-300+tt, 301, 2):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp

for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        j = abs(x-y)
        x, y = (min(x, y), max(x, y))
        if i-j >= 1:
            ansdouble += coinacumdictli[i-j][y]+coinacumdictli[i-j][y-2] - coinacumdictli[i-j][x] - coinacumdictli[i-j][x-2]
        if i+j <= h+w-1:
            ansdouble += coinacumdictli[i+j][y]+coinacumdictli[i+j][y-2] - coinacumdictli[i+j][x] - coinacumdictli[i+j][x-2]

print(ansdouble//2)

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)

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    for j in range(-300, 301):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp

ansdouble = 0
for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        j = abs(x-y)
        x, y = (min(x, y), max(x, y))
        if i-j >= 1:
            ansdouble += coinacumdictli[i-j][y]+coinacumdictli[i-j][y-1] - coinacumdictli[i-j][x] - coinacumdictli[i-j][x-1]
        if i+j <= h+w-1:
            ansdouble += coinacumdictli[i+j][y]+coinacumdictli[i+j][y-1] - coinacumdictli[i+j][x] - coinacumdictli[i+j][x-1]

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

coinacumdictli = [{} for i in range(h+w)]
for i in range(1, h+w):
    tmp = 0
    for j in range(-300, 301):
        if j in coinsetli[i]:
            tmp += 1
        coinacumdictli[i][j] = tmp

for i in range(1, h+w):
    for x, y in combinations(coinsetli[i], 2):
        j = abs(x-y)
        x, y = (min(x, y), max(x, y))
        if i-j >= 1:
            ansdouble += coinacumdictli[i-j][y]+coinacumdictli[i-j][y-1] - coinacumdictli[i-j][x] - coinacumdictli[i-j][x-1]
        if i+j <= h+w-1:
            ansdouble += coinacumdictli[i+j][y]+coinacumdictli[i+j][y-1] - coinacumdictli[i+j][x] - coinacumdictli[i+j][x-1]

print(ansdouble//2)

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:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

# for f in field:
#   print(f)

ans = 0
for i in range(N):
  for j in range((i+W)%2, N, 2):
    for k in range(j+2, N, 2):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k+1] - accCol[i-d][j]
        if i + d < N:
          ans += accCol[i+d][k+1] - accCol[i+d][j]

for i in range(N):
  for j in range((i+W)%2, N, 2):
    if field[i][j] != 1:
      continue
    for d in range(2, N, 2):
      if i + d < N and j + d < N and field[i][j+d] == field[i+d][j] == 1:
        ans -= 1
      if i + d < N and j - d >= 0 and field[i][j-d] == field[i+d][j] == 1:
        ans -= 1
      if i - d >= 0 and j - d >= 0 and field[i][j-d] == field[i-d][j] == 1:
        ans -= 1
      if i - d >= 0 and j + d < N and field[i][j+d] == field[i-d][j] == 1:
        ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

ans = 0
for i in range(N):
  for j in range(N):
    for k in range(j+1, N):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k+1] - accCol[i-d][j]
        if i + d < N:
          ans += accCol[i+d][k+1] - accCol[i+d][j]

for i in range(N):
  for j in range(N):
    if field[i][j] != 1:
      continue
    for d in range(1, N):
      if i + d < N and j + d < N and field[i][j+d] == field[i+d][j] == 1:
        ans -= 1
      if i + d < N and j - d >= 0 and field[i][j-d] == field[i+d][j] == 1:
        ans -= 1
      if i - d >= 0 and j - d >= 0 and field[i][j-d] == field[i-d][j] == 1:
        ans -= 1
      if i - d >= 0 and j + d < N and field[i][j+d] == field[i-d][j] == 1:
        ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def check(field, i, j):
    try:
        return field[i][j] == '#'
    except:
        return False


h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            continue
        d = max(i + j, h - i + j - 1, i + w - j - 1, h - i + w - j - 2)
        for k in range(2, d + 1, 2):
            coe = set()
            ti = i - k
            ui = i + k
            for l in range(1, k + 1):
                ci = ti + l
                cj = j + l
                if 0 <= ci < h and 0 <= cj < w and field[ci][cj] == '#':
                    for di, dj in coe:
                        if abs(ci - di) + abs(cj - dj) == k:
                            ans += 1
                    coe.add((ci, cj))
                ci = ui - l + 1
                cj = j + l - 1
                if 0 <= ci < h and 0 <= cj < w and field[ci][cj] == '#':
                    for di, dj in coe:
                        if abs(ci - di) + abs(cj - dj) == k:
                            ans += 1
                    coe.add((ci, cj))
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 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:
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(i+j, H-i, W-j)+2):
            if countR(n, i, j) and countD(n, i, j):
                ans += countLU(n, i, j)
for i in range(H):
    for j in range(W):
        for n in range(1, min(i, W-j, H-i+j)+2):
            if countR(n, i, j) and countU(n, i, j):
                ans += countLD(n, i, j)
for i in range(H):
    for j in range(W):
        for n in range(1, min(i+W-j, H-i, j)+2):
            if countL(n, i, j) and countD(n, i, j):
                ans += countRU(n, i, j)
for i in range(H):
    for j in range(W):
        for n in range(1, min(i, j, H-i + W-j)+2):
            if countL(n, i, j) and countU(n, i, j):
                ans += countRD(n, i, j)
for i in range(H):
    for j in range(W):
        for n in range(1, max(H, W)):
            if countR(n, i, j) and countD(n, i, j) and countL(n, i, j):
                ans += 1
for i in range(H):
    for j in range(W):
        for n in range(1, max(H, W)):
            if countR(n, i, j) and countD(n, i, j) and countU(n, i, j):
                ans += 1
for i in range(H):
    for j in range(W):
        for n in range(1, max(H, W)):
            if countR(n, i, j) and countU(n, i, j) and countL(n, i, j):
                ans += 1
for i in range(H):
    for j in range(W):
        for n in range(1, max(H, W)):
            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 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 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//3)

Submission status: Time Limit Exceeded

Solution code:
import math
(h, w) = map(int, input().split())
s = []

def ran(s1, s2):
    return abs(s1[0] - s2[0]) + abs(s1[1] - s2[1])

for i in range(h):
    tmp = list(input())
    for j in range(w):
        if tmp[j] == '#':
            s.append([i, j])
count = 0
for i in range(len(s) - 2):
    for j in range(i + 1, len(s) - 1):
        for k in range(j + 1, len(s)):
            si = s[i]
            sj = s[j]
            sk = s[k]

            ranij = ran(si, sj)
            ranjk = ran(sj, sk)
            ranik = ran(si, sk)
            if ranij == ranjk and ranij == ranik and ranik == ranjk:
                count += 1

print(count)

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, max(H, W)):
            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)