Problem:


枠

画像の中から有益な情報を抽出する画像認識はコンピュータサイエンスの中でも重要な研究テーマのひとつです。デジタルカメラ、運転支援システム、防犯システムなどに幅広く応用されています。

このような研究のおかげで、私たちは画像解析を行うための多くのソフトウェアやプログラム集を使い様々な処理を行うことができます。一方、自力でプログラムを書いて解析することで、その仕組みを知り、楽しい時間を過ごすことができます。ここでは、一風変わった画像認識をしてみましょう。

画像として次のような各ピクセルが整数の値を持つ N &times; N のピクセルが入力として与えられます。この画像の中から、線の太さが１ピクセルの長方形の枠（わく）を１つ抽出します。

枠が覆うピクセルの値の和が最大となるような枠を抽出して、その和を報告するプログラムを作成して
下さい。ただし、下の図のように、縦、横のピクセル数が１つや２つの場合も枠とみなすものとします。

入力

入力は以下の形式で与えられる。

N
p1,1 p1,2 ... p1,N
p2,1 p2,2 ... p2,N
:
pN,1 pN,2 ... pN,N

１行目に縦と横のピクセル数 N (1 ≤ N ≤ 300) が与えられる。続く N 行に、i 行 j 列目のピクセルの値を表す整数 pi,j (-1000 ≤ pi,j ≤ 1000)が与えられる。

出力

ピクセル値の和が最大となるような枠の、ピクセル値の和を１行に出力する。

入出力例

入力例１

5
2 0 0 2 0
0 1 0 2 0
0 0 0 -1 0
0 4 0 3 0 
-1 0 0 1 0

 出力例１ 

12

入力例２

3
0 0 0
0 -1 0
0 0 0

出力例２

0



Sample input:
5
2 0 0 2 0
0 1 0 2 0
0 0 0 -1 0
0 4 0 3 0
-1 0 0 1 0


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys
f = sys.stdin

n = int(f.readline())
p = [list(map(int, line.split())) for line in f]

row = [[0 for j in range(n + 1)] for i in range(n)]
col = [[0 for j in range(n)] for i in range(n + 1)]

for i in range(n):
    for j in range(n):
        row[i][j + 1] = row[i][j] + p[i][j]
        col[i + 1][j] = col[i][j] + p[i][j]

max_flame = 0
for u in range(n):
    horizontal_lines =(row[u][r + 1] - row[u][l] for l in range(n) for r in range(l,n))
    max_flame = max(max_flame, max(horizontal_lines))
    for d in range(u + 1,n):
        l_c = col[d + 1][0] - col[u][0] # ?????§??????????????????C???????????¨?????¨??????????£??????\???????????????
        max_flame = max(max_flame,l_c)
        for r in range(1,n):
            r_vertical = col[d + 1][r] - col[u][r]
            max_flame = max(max_flame, l_c + r_vertical)
            l_c = max(l_c, l_c + p[u][r] + p[d][r])
print(max_flame)

Submission status: Wrong Answer

Solution code:
import sys
f = sys.stdin

n = int(f.readline())
p = [list(map(int, line.split())) for line in f]

row = [[0 for j in range(n + 1)] for i in range(n)]
col = [[0 for j in range(n)] for i in range(n + 1)]

for i in range(n):
    for j in range(n):
        row[i][j + 1] = row[i][j] + p[i][j]
        col[i + 1][j] = col[i][j] + p[i][j]

max_flame = -float('inf')
for u in range(n):
    horizontal_lines =(row[u][r + 1] - row[u][l] for l in range(n) for r in range(l,n))
    max_flame = max(max_flame, max(horizontal_lines))
    for d in range(u + 1,n):
        l_c = col[d + 1][0] - col[u][0] # ?????§??????????????????C???????????¨?????¨??????????£??????\???????????????
        max_flame = max(max_flame,l_c)
        for r in range(1,n):
            r_vertical = col[d + 1][r] - col[u][r]
            max_flame = max(max_flame, l_c + r_vertical)
            l_c = max(l_c, l_c + p[u][r] + p[d][r])
print(max_flame)

Submission status: Wrong Answer

Solution code:
import sys
#@profile
def main():
    f = sys.stdin

    n = int(f.readline())
    p = [list(map(int, line.split())) for line in f]

    row = [[0 for j in range(n + 1)] for i in range(n)]
    col = [[0 for j in range(n)] for i in range(n + 1)]

    for i in range(n):
        for j in range(n):
            row[i][j + 1] = row[i][j] + p[i][j]
            col[i + 1][j] = col[i][j] + p[i][j]

    frames = []
    f_append = frames.append
    horizontal_lines =(row[u][r] - row[u][l] for u in range(n) for l in range(n) for r in range(l + 1,n + 1))
    f_append(max(horizontal_lines))
    
    for u in range(n):
        for d in range(u + 1,n):
            l_c = col[d + 1][0] - col[u][0]
            f_append(l_c)
            for r in range(1,n):
                r_vertical = col[d + 1][r] - col[u][r]
                f_append(l_c + r_vertical)
                l_c = max(l_c + p[u][r] + p[d][r], r_vertical)
        frames = [max(frames)]
    print(max(frames))
main()

Submission status: Wrong Answer

Solution code:
def solve():
    from sys import stdin
    from itertools import accumulate
    
    file_input = stdin
    
    N = int(file_input.readline())
    
    img = []
    acc_row = []
    
    for line in file_input:
        line = list(map(int, line.split()))
        img.append(line)
        acc_row.append(list(accumulate(line)) + [0])
    
    def acc_list(col):
        return list(accumulate(col)) + [0]
    acc_col = list(map(acc_list, zip(*img)))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_row_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_row_j, acc_row_j = tpl_2
            
            single_row = acc_row_i[j] - acc_row_i[i - 1]
            if single_row > ans:
                ans = single_row
            
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for k, acc_col_k in enumerate(acc_col[1:], start=1):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                c_col_max = col_max + img_row_i[k] + img_row_j[k]
                if c_col_max > col_max:
                    col_max = c_col_max
    print(ans)

solve()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    G = tuple(tuple(map(int, line.split())) for line in file_input)
    
    # accumulated rows
    ar = ((0,) + tuple(accumulate(line)) for line in G)
    
    # accumulated columns
    ac = ((0,) + tuple(accumulate(line)) for line in zip(*G))
    ac_1 = next(ac)
    ac = tuple(zip(*ac))
    
    ans = 0
    for i, t1 in enumerate(zip(G, ar, ac, ac_1)):
        G_i, ar_i, ac_i, ac_1i = t1
        ar_ii = ar_i[i]
        for j, t2 in enumerate(zip(G[i:], ar_i[i+1:], ac[i+1:], ac_1[i+1:])):
            G_j, ar_ij, ac_j, ac_1j = t2
            if ar_ij - ar_ii > ans:
                ans = ar_ij - ar_ii
                
            if i == j:
                continue
            
            col_max = ac_1j - ac_1i
            
            for ac_jk, ac_ik, G_ik, G_jk in zip(ac_j, ac_i, G_i[1:], G_j[1:]):
                col = ac_jk - ac_ik
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + G_ik + G_jk
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
f = sys.stdin

n = int(f.readline())
p = [list(map(int, line.split())) for line in f]

row = [[0 for j in range(n + 1)] for i in range(n)]
col = [[0 for j in range(n)] for i in range(n + 1)]

for i in range(n):
    for j in range(n):
        row[i][j + 1] = row[i][j] + p[i][j]
        col[i + 1][j] = col[i][j] + p[i][j]

max_flame = -float('inf')
for u in range(n):
    horizontal_lines =(row[u][r + 1] - row[u][l] for l in range(n) for r in range(l,n))
    max_flame = max(max_flame, max(horizontal_lines))
    for d in range(u + 1,n):
        l_c = col[d + 1][0] - col[u][0] # ?????§??????????????????C???????????¨?????¨??????????£??????\???????????????
        max_flame = max(max_flame,l_c)
        for r in range(1,n):
            r_vertical = col[d + 1][r] - col[u][r]
            max_flame = max(max_flame, l_c + r_vertical)
            l_c = max(l_c + p[u][r] + p[d][r], r_vertical)
print(max_flame)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    f = sys.stdin

    n = int(f.readline())
    p = [list(map(int, line.split())) for line in f]

    row = [[0 for j in range(n + 1)] for i in range(n)]
    col = [[0 for j in range(n)] for i in range(n + 1)]

    for i in range(n):
        for j in range(n):
            row[i][j + 1] = row[i][j] + p[i][j]
            col[i + 1][j] = col[i][j] + p[i][j]

    frames = []
    horizontal_lines =(row[u][r] - row[u][l] for u in range(n) for l in range(n) for r in range(l + 1,n + 1))
    frames.append(max(horizontal_lines))
    
    for u in range(n):
        for d in range(u + 1,n):
            l_c = col[d + 1][0] - col[u][0]
            frames.append(l_c)
            for r in range(1,n):
                r_vertical = col[d + 1][r] - col[u][r]
                frames.append(l_c + r_vertical)
                l_c = max(l_c + p[u][r] + p[d][r], r_vertical)
        frames = [max(frames)]
    print(max(frames))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    f = sys.stdin

    n = int(f.readline())
    p = [list(map(int, line.split())) for line in f]

    row = [[0 for j in range(n + 1)] for i in range(n)]
    col = [[0 for j in range(n)] for i in range(n + 1)]

    for i in range(n):
        for j in range(n):
            row[i][j + 1] = row[i][j] + p[i][j]
            col[i + 1][j] = col[i][j] + p[i][j]

    frames = []
    
    # ?°´??????????¨???? 
    for i in range(n):
        now = 0
        for j in range(n):
            now += p[i][j]
            frames.append(now)
            if now < 0:
                now = 0
    
    for u in range(n):
        for d in range(u + 1,n):
            verticals = [col[d + 1][i] - col[u][i] for i in range(n)]
            
            l_c = [0, verticals[0]]
            
            for pu,pd,v in zip(p[u][1:],p[d][1:],verticals[1:]):
                l_c.append(max(l_c[-1] + pu + pd, v))
                
            frames.extend(v1 + v2 for v1,v2 in zip(l_c,verticals))
        frames = [max(frames)] 
    print(max(frames))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys  
from itertools import accumulate
def main():
    f = sys.stdin
    
    n = int(f.readline())
    p = [list(map(int, line.split())) for line in f]
    
    col = list(zip(*list([0] + list(accumulate(pi)) for pi in zip(*p))))
    
    
    frames = []
    
    # ?°´??????????¨???? 
    for pi in p:
        now = 0
        for pij in pi:
            now += pij
            frames.append(now)
            if now < 0:
                now = 0
                
    for u in range(n):
        for d in range(u + 1,n):
            verticals = [cold - colu for cold,colu in zip(col[d + 1],col[u])]
            l_c = [0, verticals[0]]
            for pu,pd,v in zip(p[u][1:],p[d][1:],verticals[1:]):
                l_c.append(max(l_c[-1] + pu + pd, v))
            frames.append(max(map(sum, zip(l_c,verticals))))
        frames = [max(frames)]
    print(max(frames))
main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    from itertools import accumulate
    
    file_input = stdin
    
    N = int(file_input.readline())
    
    img = []
    acc_row = []
    
    for line in file_input:
        line = list(map(int, line.split()))
        img.append(line)
        acc_row.append(list(accumulate(line)) + [0])
    
    def acc_list(col):
        return list(accumulate(col)) + [0]
    acc_col = list(map(acc_list, zip(*img)))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_row_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_row_j, acc_row_j = tpl_2
            
            single_row = acc_row_i[j] - acc_row_i[i - 1]
            if single_row > ans:
                ans = single_row
            
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for k, acc_col_k in enumerate(acc_col[1:], start=1):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_row_i[k] + img_row_j[k]
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    from itertools import accumulate
    
    file_input = stdin
    
    N = int(file_input.readline())
    
    img = []
    acc_row = []
    
    for line in file_input:
        line = tuple(map(int, line.split()))
        img.append(line)
        acc_row.append(tuple(accumulate(line)) + (0,))
    
    def acc_list(col):
        return tuple(accumulate(col)) + (0,)
    acc_col = tuple(map(acc_list, zip(*img)))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_row_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_row_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
            
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_row_i_k, img_row_j_k in zip(acc_col[1:], img_row_i[1:], img_row_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_row_i_k + img_row_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    from itertools import accumulate
     
    file_input = stdin
     
    N = int(file_input.readline())
     
    img = []
    acc_row = []
     
    for line in file_input:
        line = tuple(map(int, line.split()))
        img.append(line)
        acc_row.append(tuple(accumulate(line)) + (0,))
     
    def acc_list(col):
        return tuple(accumulate(col)) + (0,)
    acc_col = tuple(map(acc_list, zip(*img)))
     
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_row_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_row_j, acc_row_j = tpl_2
             
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
             
            if i == j:
                continue
             
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
             
            for acc_col_k, img_row_i_k, img_row_j_k in zip(acc_col[1:], img_row_i[1:], img_row_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                 
                t_col_max = col_max + img_row_i_k + img_row_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)
 
solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    from itertools import accumulate
     
    file_input = stdin
     
    N = int(file_input.readline())
     
    img = []
    acc_row = []
     
    for line in file_input:
        line = tuple(map(int, line.split()))
        img.append(line)
        acc_row.append(tuple(accumulate(line)) + (0,))
    img = tuple(img)
    acc_row = tuple(acc_row)
     
    def acc_list(col):
        return tuple(accumulate(col)) + (0,)
    acc_col = tuple(map(acc_list, zip(*img)))
     
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_row_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_row_j, acc_row_j = tpl_2
             
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
             
            if i == j:
                continue
             
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
             
            for acc_col_k, img_row_i_k, img_row_j_k in zip(acc_col[1:], img_row_i[1:], img_row_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                 
                t_col_max = col_max + img_row_i_k + img_row_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)
 
solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
     
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = tuple(tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
     
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = tuple(tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    N = int(stdin.readline())
    img = tuple(tuple(map(int, line.split())) for line in stdin)
    
    acc_row = tuple(tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, tpl_2 in enumerate(zip(img[i:], acc_row[i:]), start=i):
            img_j, acc_row_j = tpl_2
            
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = tuple(tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, img_j in enumerate(img[i:], start=i):
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = (tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, img_j in enumerate(img[i:], start=i):
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Memory Limit Exceeded

Solution code:
import sys
def main():
    f = sys.stdin

    n = int(f.readline())
    p = [list(map(int, line.split())) for line in f]

    row = [[0 for j in range(n + 1)] for i in range(n)]
    col = [[0 for j in range(n)] for i in range(n + 1)]

    for i in range(n):
        for j in range(n):
            row[i][j + 1] = row[i][j] + p[i][j]
            col[i + 1][j] = col[i][j] + p[i][j]

    frames = []
    f_append = frames.append
    horizontal_lines =(row[u][r] - row[u][l] for u in range(n) for l in range(n) for r in range(l + 1,n + 1))
    f_append(max(horizontal_lines))
    
    for u in range(n):
        for d in range(u + 1,n):
            l_c = col[d + 1][0] - col[u][0]
            f_append(l_c)
            for r in range(1,n):
                r_vertical = col[d + 1][r] - col[u][r]
                f_append(l_c + r_vertical)
                l_c = max(l_c + p[u][r] + p[d][r], r_vertical)
    print(max(frames))
main()

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = (tuple(accumulate(line)) + (0,) for line in img)
    
    acc_col = (tuple(accumulate(line)) + (0,) for line in zip(*img))
    acc_col_1 = next(acc_col)
    acc_col = tuple(zip(*acc_col))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, img_j in enumerate(img[i:], start=i):
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col_max = acc_col_1[j] - acc_col_1[i - 1]
            
            for acc_col_j_k, acc_col_i_k, img_i_k, img_j_k in zip(acc_col[j], acc_col[i - 1], img_i[1:], img_j[1:]):
                col = acc_col_j_k - acc_col_i_k
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    G = tuple(tuple(map(int, line.split())) for line in file_input)
    
    # accumulated rows
    ar = ((0,) + tuple(accumulate(line)) for line in G)
    
    # accumulated columns
    ac = ((0,) + tuple(accumulate(line)) for line in zip(*G))
    ac_1 = next(ac)
    ac = tuple(zip(*ac))
    
    ans = 0
    for i, t1 in enumerate(zip(G, ar, ac, ac_1)):
        G_i, ar_i, ac_i, ac_1i = t1
        ar_ii = ar_i[i]
        for j, t2 in enumerate(zip(G[i:], ar_i[i+1:], ac[i+1:], ac_1[i+1:]), start=i):
            G_j, ar_ij, ac_j, ac_1j = t2
            if ar_ij - ar_ii > ans:
                ans = ar_ij - ar_ii
                
            if i == j:
                continue
            
            col_max = ac_1j - ac_1i
            
            for ac_jk, ac_ik, G_ik, G_jk in zip(ac_j, ac_i, G_i[1:], G_j[1:]):
                col = ac_jk - ac_ik
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + G_ik + G_jk
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate

def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    G = tuple(tuple(map(int, line.split())) for line in file_input)
    G1 = tuple(t[1:] for t in G)
    
    # accumulated rows
    ar = ((0,) + tuple(accumulate(line)) for line in G)
    
    # accumulated columns
    ac = ((0,) + tuple(accumulate(line)) for line in zip(*G))
    ac_1 = next(ac)
    ac = tuple(zip(*ac))
    
    ans = 0
    for i, t1 in enumerate(zip(G1, ar, ac, ac_1)):
        G_i, ar_i, ac_i, ac_1i = t1
        ar_ii = ar_i[i]
        for j, t2 in enumerate(zip(G1[i:], ar_i[i+1:], ac[i+1:], ac_1[i+1:]), start=i):
            G_j, ar_ij, ac_j, ac_1j = t2
            single_row = ar_ij - ar_ii
            if single_row > ans:
                ans = single_row
                
            if i == j:
                continue
            
            col_max = ac_1j - ac_1i
            
            for ac_jk, ac_ik, G_ik, G_jk in zip(ac_j, ac_i, G_i, G_j):
                col = ac_jk - ac_ik
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + G_ik + G_jk
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()

Submission status: Runtime Error

Solution code:
def solve():
    file_input = stdin
    
    N = int(file_input.readline())
    img = tuple(tuple(map(int, line.split())) for line in file_input)
    
    acc_row = (tuple(accumulate(line)) + (0,) for line in img)
    acc_col = tuple(tuple(accumulate(line)) + (0,) for line in zip(*img))
    
    ans = 0
    for i, tpl_1 in enumerate(zip(img, acc_row)):
        img_i, acc_row_i = tpl_1
        for j, img_j in enumerate(img[i:], start=i):
            if acc_row_i[j] - acc_row_i[i - 1] > ans:
                ans = acc_row_i[j] - acc_row_i[i - 1]
                
            if i == j:
                continue
            
            col = acc_col[0]
            col_max = col[j] - col[i - 1]
            
            for acc_col_k, img_i_k, img_j_k in zip(acc_col[1:], img_i[1:], img_j[1:]):
                col = acc_col_k[j] - acc_col_k[i - 1]
                
                if col_max > 0:
                    c_ans = col_max + col
                    if c_ans > ans:
                        ans = c_ans
                else:
                    if col > ans:
                        ans = col
                
                t_col_max = col_max + img_i_k + img_j_k
                if t_col_max > col:
                    col_max = t_col_max
                else:
                    col_max = col
    print(ans)

solve()