Problem:


Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

S_i is a string of length W consisting of # and ..

. occurs at least once in one of the strings S_i (1 \leq i \leq H).

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the maximum possible number of squares lighted by the lamp.

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Runtime Error

Solution code:
import numpy as np

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]

X = np.zeros((W, H))
for i in range(H):
    start = 0
    cnt = 0
    for j in range(W):
        if s[i][j] == "." and j == W - 1:
            cnt += 1
            for k in range(start, W):
                if s[i][k] == ".":
                    X[i][k] = cnt
        elif s[i][j] == ".":
            cnt += 1
        elif s[i][j] == "#":
            for k in range(start, j):
                if s[i][k] == ".":
                    X[i][k] = cnt
            start = j
            cnt = 0

Y = np.zeros((W, H))
for i in range(W):
    start = 0
    cnt = 0
    for j in range(H):
        if s[j][i] == "." and j == H - 1:
            cnt += 1
            for k in range(start, H):
                if s[k][i] == ".":
                    Y[k][i] = cnt
        elif s[j][i] == ".":
            cnt += 1
        elif s[j][i] == "#":
            for k in range(start, j):
                if s[k][i] == ".":
                    Y[k][i] = cnt
            start = j
            cnt = 0

XY = X + Y - 1
print(int(np.max(XY)))

Submission status: Runtime Error

Solution code:
H,W=map(int,input().split())
S=[]
for i in range(H):
    s=input()
    S.append(s)
L=[[] for _ in range(H)]
R=[[] for _ in range(H)]
D=[[] for _ in range(H)]
U=[[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            L[i].append(0)
        if S[i][W-1-j]=="#":
            R[i].append(0)
        else:
            if j==0:
                L[i].append(1)
                R[i].append(1)
            else:
                L[i].append(L[i][j-1]+1)
                R[i].append(R[i][j-1]+1)

for i in range(W):
    for j in range(H):
        if S[j][i]=="#":
            U[j].append(0)
        if S[H-1-j][i]=="#":
            D[j].append(0)
        else:
            if j==0:
                U[j].append(1)
                D[j].append(1)
            else:
                U[j].append(U[j-1][i]+1)
                D[j].append(D[j-1][i]+1)
ans=0

for i in range(H):
    for j in range(W):
        tmp=L[i][j]+R[i][W-1-j]+U[i][j]+D[H-1-i][j]-3
        ans=max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===
input_num = getInputListInt()

h = input_num[0]
w = input_num[1]

data=[]
for i in range(h):
    tmp = str(input())
    tmp_list = list(tmp)
    data.append(tmp_list)

def saikiU(cnt, i, j):
    if i < 0 or i > h-1: return cnt
    if j < 0 or j > w-1: return cnt
    if data[i][j] == "#": return cnt

    return saikiU(cnt+1, i-1, j)


def saikiD(cnt, i, j):
    if i < 0 or i > h - 1: return cnt
    if j < 0 or j > w - 1: return cnt
    if data[i][j] == "#": return cnt

    return saikiD(cnt + 1, i + 1, j)

def saikiL(cnt, i, j):
    if i < 0 or i > h - 1: return cnt
    if j < 0 or j > w - 1: return cnt
    if data[i][j] == "#": return cnt

    return saikiL(cnt + 1, i, j-1)

def saikiR(cnt, i, j):
    if i < 0 or i > h - 1: return cnt
    if j < 0 or j > w - 1: return cnt
    if data[i][j] == "#": return cnt

    return saikiR(cnt + 1, i, j+1)

ans = 0
for i in range(h):
    for j in range(w):
        if data[i][j] == "#": continue
        tmp_ans = -3
        tmp_ans += saikiU(0, i, j)
        tmp_ans += saikiD(0, i, j)
        tmp_ans += saikiL(0, i, j)
        tmp_ans += saikiR(0, i, j)
        ans = max(ans, tmp_ans)

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = ["" for j in range(h)]
ma = 0
for i in range(h):
    s = stdin.readline().rstrip()
    li[i] = s
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":
            continue
        now_u = 0;now_b = 0;now_r = 0;now_l = 0
        while i+now_b <= h-1:
            if li[i+now_b][j] == ".":
                now_b += 1
            else:
                break
        while i-now_u >= 0:
            if li[i-now_u][j] == ".":
                now_u += 1
            else:
                break
        while j+now_r <= w-1:
            if li[i][j+now_r] == ".":
                now_r += 1
            else:
                break
        while i-now_l >= 0:
            if li[i][j-now_l] == ".":
                now_l += 1
            else:
                break
        point = now_u+now_b+now_r+now_l-3
        ma = max(point,ma)
print(ma)

Submission status: Runtime Error

Solution code:
from sys import stdin
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]
li = ["" for j in range(h)]
ma = 0
for i in range(h):
    s = stdin.readline().rstrip()
    li[i] = s
for i in range(h):
    for j in range(w):
        now_u = 0;now_b = 0;now_r = 0;now_l = 0
        while i+now_b < h:
            if li[i+now_b][j] == ".":
                now_b += 1
            else:
                now_b -= 1
                break
        while i-now_u >= 0:
            if li[i-now_u][j] == ".":
                now_u += 1
            else:
                now_u -= 1
                break
        while j+now_r < w:
            if li[i][j+now_r] == ".":
                now_r += 1
            else:
                now_r -= 1
                break
        while i-now_l >= 0:
            if li[i][j-now_l] == ".":
                now_l += 1
            else:
                now_l -= 1
                break
        point = now_u+now_b+now_r+now_l-2
        ma = max(ma,point)
print(ma)

Submission status: Runtime Error

Solution code:
import numpy as np
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
print(S)
print()
L = np.zeros((H,W),dtype=np.int)
R = np.zeros((H,W),dtype=np.int)
U = np.zeros((H,W),dtype=np.int)
D = np.zeros((H,W),dtype=np.int)
print(L)
print(L[2][1])
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            L[i][j] = 0
        else:
            L[i][j] = L[i][j-1]+1
        if S[-i-1][-j-1] == "#":
            R[-i-1][-j-1] = 0
        else:
            R[-i-1][-j-1] = R[-i-1][-j]+1

for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            U[i][j] = 0
        else:
            U[i][j] = U[i-1][j]+1
        if S[-i-1][-j-1] == "#":
            D[-i-1][-j-1] = 0
        else:
            D[-i-1][-j-1] = D[-i][-j-1]+1
print(np.max(L+R+U+D)-3)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
s = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
s = np.pad(s, 1)

def main():
    l = np.zeros((h+2, w+2), dtype=np.int64)
    r = np.zeros((h+2, w+2), dtype=np.int64)
    u = np.zeros((h+2, w+2), dtype=np.int64)
    d = np.zeros((h+2, w+2), dtype=np.int64)

    for i in range(1, w+1):
        bl = s[:, i] == '#'
        l[~bl, i] = l[~bl, i-1] + 1
        i = w+1-i
        bl = s[:, i] == '#'
        r[~bl, i] = r[~bl, i+1] + 1
    
    for i in range(1, h+1):
        bl = s[i, :] == '#'
        u[i, ~bl] = u[i-1, ~bl] + 1
        i = h+1-i
        bl = s[i, :] == '#'
        d[i, ~bl] = d[i+1, ~bl] + 1
    
    res = l + r + u + d - 3
    return np.amax(res[1:h+1, 1:w+1])

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
s = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
s = np.pad(s, 1, mode='constant', constant_values=('#'))

def main():
    l = np.zeros((h+2, w+2), dtype=np.int64)
    r = np.zeros((h+2, w+2), dtype=np.int64)
    u = np.zeros((h+2, w+2), dtype=np.int64)
    d = np.zeros((h+2, w+2), dtype=np.int64)

    for i in range(1, w+1):
        bl = s[:, i] == '#'
        l[~bl, i] = l[~bl, i-1] + 1
        i = w+1-i
        bl = s[:, i] == '#'
        r[~bl, i] = r[~bl, i+1] + 1
    
    for i in range(1, h+1):
        bl = s[i, :] == '#'
        u[i, ~bl] = u[i-1, ~bl] + 1
        i = h+1-i
        bl = s[i, :] == '#'
        d[i, ~bl] = d[i+1, ~bl] + 1
    
    res = l + r + u + d - 3
    return np.amax(res)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0

# 尺取り法
right = 0
tmp = 0
for i in range(N):
    for k in range(right, N, 1):
        tmp += A[k]
        if tmp >= K:
            right = k
            ans += N - right
            tmp -= A[i]
            tmp -= A[right]
            break
        if k == N-1:
            tmp -= A[k]
            tmp -= A[i]
            right = k
            break 


print(ans)

Submission status: Runtime Error

Solution code:
def main():
    H,W = map(int,input().split())
    S = [[1 if s == "." else 0 for s in input()] for _ in range(H)]
    R = [[0]*W for _ in range(H)]
    L = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]
    U = [[0]*W for _ in range(H)]

    for h in range(H):
        for w in range(1,W - 1):
            if S[h][w] and S[h][w - 1]:
                L[h][w] += L[h][w - 1] + 1
            if S[h][W - w] and S[h][W - w - 1]:
                R[h][W - w - 1] += R[h][W - w] + 1
        if S[h][W -1] and S[h][W - 2]:
            L[h][W - 1] += L[h][W - 2] + 1
        if S[h][0] and S[h][1]:
            R[h][0] += R[h][1] + 1
    for w in range(W):
        for h in range(1,H-1):
            if S[h-1][w] and S[h][w]:
                U[h][w] += U[h-1][w] + 1
            if S[H - h][w] and S[H - h - 1][w]:
                D[H - h - 1][w] += D[H - h][w] + 1
        if S[H - 1][w] and S[H - 2][w]:
            D[H - 1][w] += D[H-2][w] + 1
        if S[0][w] and S[1][w]:
            U[0][w] += U[1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,U[h][w] + D[h][w] + R[h][w] + L[h][w])
    print(ans + 1)
    return 

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    H,W = map(int,input().split())

    S = [[] for i in range(H)]

    for i in range(H):
        S[i] = list(input())

    M = 0
    for i in range(H):
        for j in range(W):
            cou = 0
            if S[i][j] == '.':
                for n in range(H-i-1):
                    if S[i+n+1][j] == '.':
                        cou += 1
                    else:
                        break
                if cou > i + cou + W:
                    break

                for n in range(W-j-1):
                    if S[i][j+n+1] == '.':
                        cou += 1
                    else:
                        break
                if cou > i + j + cou:
                    break

                for n in range(j):
                    if S[i][j-n-1] == '.':
                        cou += 1
                    else:
                        break
                if cou > j + cou:
                    break

                for n in range(i):
                    if S[i-n-1][j] == '.':
                        cou += 1
                    else:
                        break
            if cou > M:
                M = cou
                if M = H+W-2:
                    break

    print(M+1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
h, w = map(int, input().split())
grid = []
for i in range(h):
  gridi = input()
  grid.append(gridi)
xcnt = [[0]*w for i in range(h)]
ycnt = [[0]*w for i in range(h)]
ans = -10**9
# print(grid, h, w)
for y in range(h):
  cnt = 0
  for x in range(w-1):
    if grid[y][x] == "#":
      cnt = 0
      continue
    if grid[y][x+1] == "#":
      xcnt[y][x] = cnt + 1
      cnt = 0
    else:
      cnt += 1
  if grid[y][x+1] == ".":
    xcnt[y][x+1] = cnt + 1
# print(xcnt)
for y in range(h):
  for x in range(w-1):
    if grid[y][w-1-x] == "#":
      continue
    if grid[y][w-1-x-1] == ".":
      xcnt[y][w-1-x-1] = xcnt[y][w-1-x]
# print(*xcnt)

for x in range(w):
  cnt = 0
  for y in range(h-1):
    if grid[y][x] == "#":
      cnt = 0
      continue
    if grid[y+1][x] == "#":
      ycnt[y][x] = cnt + 1
      cnt = 0
    else:
      cnt += 1
  if grid[y+1][x] == ".":
    ycnt[y+1][x] = cnt + 1
# print(ycnt)
for x in range(w):
  for y in range(h-1):
    if grid[h-1-y][x] == "#":
      continue
    if grid[h-1-y-1][x] == ".":
      ycnt[h-1-y-1][x] = ycnt[h-1-y][x]
# print(*ycnt)
for y in range(h):
  for x in range(w):
    ans = max(ans, xcnt[y][x] + ycnt[y][x] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def calculate(h, w, arr):
    L = np.zeros([h, w])
    U = np.zeros([h, w])
    D = np.zeros([h, w])
    R = np.zeros([h, w])

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)

Submission status: Runtime Error

Solution code:
H, W = [int(a) for a in input().split()]
S = [None] * H
for i in range(H):
    S[i] = input()

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]

ans = 0

for i in range(H):
    for j in range(W):
        # Uを求める
        if S[i][j] == '#':  pass  # Uは0で初期化されている
        elif i == 0:        U[i][j] = 1
        else:               U[i][j] = U[i - 1][j] + 1

        # Dを求める
        if S[H - 1 - i][j] == '#':  pass
        elif i == 0:    D[i][j] = 1
        else:           D[i][j] = D[i + 1][j] + 1

        # Lを求める
        if S[i][j] == '#':  pass
        elif j == 0:  L[i][j] = 1
        else:       L[i][j] = L[i][j - 1] + 1

        # Rを求める
        if S[i][W - 1 - j] == '#':  pass
        elif j == 0:    R[i][W - 1 - j] = 1
        else:           R[i][W - 1 - j] = R[i][W - j] + 1

        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
        
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

const int MAX_N=2005;
int n, m;
vector<string> grid;
int U[MAX_N][MAX_N], D[MAX_N][MAX_N], L[MAX_N][MAX_N], R[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    grid.resize(n);
    REP(i, n) cin >> grid[i];

    // U,L
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(grid[i-1][j-1]=='.') {
                U[i][j]=U[i-1][j]+1;
                L[i][j]=L[i][j-1]+1;
            }
        }
    }    

    // D,R 
    for(int i=n; i>0; i--) {
        for(int j=m; j>0; j--) {
            if(grid[i-1][j-1]=='.') {
                D[i][j]=D[i+1][j]+1;
                R[i][j]=R[i][j+1]+1;
            }
        }
    }    

    int ans=0;
    REP1(i,1,n) {
        REP1(j,1,m) {
            if(grid[i-1][j-1]=='.') {
                chmax(ans, U[i-1][j]+D[i+1][j]+L[i][j]+R[i][j+1]+1);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

const int MAX_N=2005;
int n, m;
vector<string> grid;
int U[MAX_N][MAX_N], D[MAX_N][MAX_N], L[MAX_N][MAX_N], R[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    grid.resize(n);
    REP(i, n) cin >> grid[i];

    // U,L
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(grid[i-1][j-1]=='.') {
                U[i][j]=U[i-1][j]+1;
                L[i][j]=L[i][j-1]+1;
            }
        }
    }    

    // D,R 
    for(int i=n; i>0; i--) {
        for(int j=m; j>0; j--) {
            if(grid[i-1][j-1]=='.') {
                D[i][j]=D[i+1][j]+1;
                R[i][j]=R[i][j+1]+1;
            }
        }
    }    

    int ans=0;
    REP1(i,1,n) {
        REP1(j,1,m) {
            if(grid[i-1][j-1]=='.') {
                chmax(ans, U[i-1][j]+D[i+1][j]+L[i][j-1]+R[i][j+1]+1);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np
H,W = map(int,input().split())
S=np.array([list(input().rstrip("\n")) for _ in range(H)]) == '.'
D = np.zeros((H,W),dtype=int)
U = np.zeros((H,W),dtype=int)
L = np.zeros((H,W),dtype=int)
R = np.zeros((H,W),dtype=int)
for i in range(H):# 上下
  U[i] = (U[i-1] + 1) * S[i]
  D[-i-1] = (D[-i] + 1) * S[-i-1]
for i in range(W):# 左右
  L[:,i] = (L[:,i-1] + 1) * S[:,i]
  '''print(L[:,i-1] + 1)
  print(S[:,i])
  print(L[:,i])'''
  R[:,-i-1] = (R[:,-i] + 1) * S[:,-i-1]
print(np.max(U+D+L+R)-3)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

def solve():
    H, W = list(map(int, sys.stdin.readline().split()))
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    grid = (np.array(grid) == ".")*1  # ランプが置ける:1, 障害物:0

    #print(grid)

    L = np.zeros((H,W), dtype=int)  # 左方向に照らせるマスの数
    R = np.zeros((H,W), dtype=int)  # 右方向に照らせるマスの数
    U = np.zeros((H,W), dtype=int)  # 上方向に照らせるマスの数
    D = np.zeros((H,W), dtype=int)  # 下方向に照らせるマスの数

    # 左方向に照らせるマスの数のDPを埋める
    for i in range(W):
        if i == 0:
            L[:, i] = grid[:, i]
        else:
            L[:, i] = (L[:, i-1] + 1) * grid[:, i]

    # 右方向に照らせるマスの数のDPを埋める
    for i in range(W-1, -1, -1):
        if i == W-1:
            R[:, i] = grid[:, i]
        else:
            R[:, i] = (R[:, i+1] + 1) * grid[:, i]

    # 上方向に照らせるマスの数のDPを埋める
    for i in range(H):
        if i == 0:
            U[i] = grid[i]
        else:
            U[i] = (U[i-1] + 1) * grid[i]

    # 下の方向に照らせるマスの数のDPを埋める
    for i in range(H-1, -1, -1):
        if i == H-1:
            D[i] = grid[i]
        else:
            D[i] = (D[i+1] + 1) * grid[i]

    # 上下左右すべてのDPを埋めた。
    # よって、i行j列目に明かりを設置したとき、上下左右に照らせるマスの数を格納した ans_grid は、
    ans_grid = L + R + U + D - 3
    ans = np.max(ans_grid)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# import numpy as np

H, W = list(map(int, input().split()))
s_table = []
total_table = []
c_table = []
for _ in range(H):
    s = list(input())
    s_table.append(s)
    total_table.append([0] * W)
    c_table.append([[0] * 4 for _ in range(W)])

for i in range(H):
    for j in range(W):
        if j != 0:
            # 左側の数を数える
            if s_table[i][j - 1] == "." and s_table[i][j] == ".":
                c_table[i][j][0] = c_table[i][j - 1][0] + 1
                total_table[i][j] += c_table[i][j][0]
        if j != 0:
            # 右側の数を数える
            if s_table[i][W - j] == "." and s_table[i][W - j - 1] == ".":
                c_table[i][W - j - 1][1] = c_table[i][W - j][1] + 1
                total_table[i][W - j - 1] += c_table[i][W - j - 1][1]
        if i != 0:
            # 上側の数を数える
            if s_table[i - 1][j] == "." and s_table[i][j] == ".":
                c_table[i][j][2] = c_table[i - 1][j][2] + 1
                total_table[i][j] += c_table[i][j][2]
        if i != 0:
            # 下側の数を数える
            if s_table[H - i][j] == "." and s_table[H - i - 1][j] == ".":
                c_table[H - i - 1][j][3] = c_table[H - i][j][3] + 1
                total_table[H - i - 1][j] += c_table[H - i - 1][j][3]
max_count = 0
for i in range(H):
    for j in range(W):
        max_count = max(max_count, total_table[i][j])
# ans = np.array(total_table).max() + 1

print(ans)

Submission status: Runtime Error

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def full(shape, full_value):
    if isinstance(shape, tuple):
        sha = shape[::-1]
        ret = [full_value] * sha[0]
        for s in sha[1:]:
            ret = [ret.copy() for i in range(s)]
        return ret
    else:
        return [full_value] * shape

H, W = read_ints()
S = read_map(H)
# まわりを壁でfill
MAP = ['#' * (W + 2)]
for s in S:
    MAP.append('#' + s + '#')
MAP.append('#' * (W + 2))


tate = full((H + 2, W + 2), 0)
yoko = full((H + 2, W + 2), 0)

# yokoの構築
for i in range(H + 2):
    pre = '#'
    for j in range(1, W + 2):
        if pre == '#' and MAP[i][j] == '.':
            s = j
            pre = '.'
        if pre == '.' and MAP[i][j] == '#':
            t = j
            cnt = t - s
            pre = '#'
            for k in range(s, t):
                yoko[i][k] = cnt

# tateの構築
for j in range(W + 2):
    pre = '#'
    for i in range(1, H + 2):
        if pre == '#' and MAP[i][j] == '.':
            s = i
            pre = '.'
        if pre == '.' and MAP[i][j] == '#':
            t = i
            cnt = t - s
            pre = '#'
            for k in range(s, t):
                tate[k][j] = cnt

ans = 0
from itertools import product
for i, j in product(range(H + 2), range(W + 2)):
    if MAP[i][j] == '#':
        continue
    ans = max(ans, tate[i][j] + yoko[i][j] - 1)

print(ans)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
typedef pair<ll,ll> P;
#define rep(i,n) for(ll (i)=0; i<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll h,w,x=0,y=0,ans=0,ans_=0;cin>>h>>w;
  string s;
  vector<P> start;
  vector<char> v(w,' ');vector<vector<char>> vv(h,v);
  lvector z(w+1,0),z_(h+1,0);vector<lvector> L(h,z),R(h,z),U(w,z_),D(w,z_);
  rep(i,h) {
    cin>>s;
    rep(j,w) {vv[i][j]=s[j]; if(s[j]=='.') start.push_back(P(i,j));}
  }
  rep(i,h) {
    rep(j,w) {
      if(vv[i][w-1-j]=='.') L[i][w-1-j]=L[i][w-j]+1;
      if(vv[i][j]=='.') R[i][j+1]=R[i][j]+1;
    }
  }
  rep(i,w) {
    rep(j,h) {
      if(vv[h-1-j][i]=='.') U[i][h-1-j]=U[i][h-j]+1;
      if(vv[j][i]=='.') D[i][j+1]=D[i][j]+1;
    }
  }
  for(auto itr:start) {
    x=itr.first,y=itr.second;
    ans_=L[x][y]+R[x][y+1]+U[y][x]+D[y][x+1]-3;
    if(ans_>ans) ans=ans_;
  }
  print(ans);
  return 0;
}

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())

maze = []
for _ in range(H):
  maze.append(list(input()))

def light(count, m, h, w, x, y, direction):
  if x < 0:
    return 0
  if x > w - 1:
    return 0
  if y < 0:
    return 0
  if y > h - 1:
    return 0
  if m[y][x] == '#':
    return 0
  if direction == 'all' or direction == 'right':
    count += light(1, m, h, w, x+1, y, 'right')
  if direction == 'all' or direction == 'left':
    count += light(1, m, h, w, x-1, y, 'left')
  if direction == 'all' or direction == 'down':
    count += light(1, m, h, w, x, y+1, 'down')
  if direction == 'all' or direction == 'up':
    count += light(1, m, h, w, x, y-1, 'up')
  return count
  
a = []  
for y, line in enumerate(maze):
  for x, point in enumerate(line):
    if point == '#':
      continue
    c = light(1, maze, H, W, x, y, 'all')
    a.append(c)

print(max(a))

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
grid = [input() for _ in range(H)]

light = [0] * 4 * (W + 1) * (H + 1)

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = (W + 1) * h + 4 * w
            light[(W + 1) * (h + 1) + 4 * w + 1] = light[here + 1] + 1
            light[(W + 1) * h + 4 * (w + 1) + 3] = light[here + 3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = (W + 1) * h + 4 * w
            light[(W + 1) * (h - 1) + 4 * w + 0] = light[here + 0] + 1
            light[(W + 1) * h + 4 * (w - 1) + 2] = light[here + 2] + 1
            ans = max(ans, light[here: here + 4])

print(ans)

Submission status: Runtime Error

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

c = []
l = []
for w in range(W):
    l.append(0)
for h in range(H):
    c.append(l)

hs = []
for i in range(W):
    hs.append(0)

for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]

#print(c)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])

print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
# dir: 0 -> start
# dir: 1 -> right
# dir: 2 -> down
# dir: 3 -> left
# dir: 4 -> up

grid = [list(input()) for _ in range(H)]


def dfs(grid,y,x,dir):
    global num_l
    if not (0 <= x < W and 0 <= y < H):
        return
    if grid[y][x] == '#':
        return
    num_l += 1
    if dir == 0:
        dfs(grid, y, x+1, 1)
        dfs(grid, y+1, x, 2)
        dfs(grid, y, x-1, 3)
        dfs(grid, y-1, x, 4)
    elif dir == 1:
        dfs(grid, y, x + 1, 1)
    elif dir == 2:
        dfs(grid, y+1, x, 2)
    elif dir == 3:
        dfs(grid, y, x-1, 3)
    elif dir == 4:
        dfs(grid, y-1, x, 4)

ans = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            num_l = 0
            dfs(grid, h, w, 0)
            ans = max(ans,num_l)
print(ans)