Problem:


Maximum Sum Sequence II

与えられた整数の行列

a1,1 a1,2 ... a1,n
a2,1 a2,2 ... a2,n
:
an,1 an,2 ... an, n

で、縦・横方向に１つ以上連続した項（部分行列）の和の最大値を出力して終了するプログラムを作成して下さい。

Input

入力データは以下の形式で与えられます。

n
a1,1 a1,2 ... a1,n
a2,1 a2,2 ... a2,n
:
an,1 an,2 ... an, n

n は 1 以上 100 以下、ai,j は -10000 以上 10000 以下です。

Output

最大値を 1 行に出力して下さい。

Sample Input 1

3
1 -2 3
-4 5 6
7 8 -9

Output for the Sample Input 1

16

この入力の場合、以下の部分行列の項の和が最大となります。

-4 5
7 8

Sample Input 2

4
1 3 -9 2
2 7 -1 5
-8 3 2 -1
5 0 -3 1

Output for the Sample Input 2

15

この入力の場合、以下の部分行列の項の和が最大となります。

7 -1 5
3 2 -1



Sample input:
3
1 -2 3
-4 5 6
7 8 -9


Sample output:
16

Submission status: Wrong Answer

Solution code:
def f(i,j):
  B=[0]*n
  m=0
  for x in range(i,n):
    a=0
    for y in range(j,n):
      a+=A[y][x]
      B[y]+=a
    m=max(B+[m])
  return m

n=int(raw_input())
N=range(n)
A=[map(int,raw_input().split()) for i in N]
m=[[f(i,j) for j in N] for i in N]
print max(max(m))

Submission status: Wrong Answer

Solution code:
def f(i,j):
  B=[0]*n
  m=-1e9
  for x in range(i,n):
    a=0
    for y in range(j,n):
      a+=A[y][x]
      B[y]+=a
    m=max(B+[m])
  return m

n=int(raw_input())
N=range(n)
A=[map(int,raw_input().split()) for i in N]
m=[[f(i,j) for j in N] for i in N]
print max(max(m))

Submission status: Wrong Answer

Solution code:
def f(i,j):
  B=[0]*n
  m=[]
  for x in range(i,n):
    a=0
    for y in range(j,n):
      a+=A[y][x]
      B[y]+=a
    m.append(max(B[j:]))
  return max(m)

n=int(raw_input())
N=range(n)
A=[map(int,raw_input().split()) for i in N]
m=[[f(i,j) for j in N] for i in N]
print max(max(m))

Submission status: Wrong Answer

Solution code:
m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N:
    s=0
    for k in range(j,n):
      s+=A[k]
      B[j][k]=max(B[j][k],0)+s
    m=max(B[j]+[m])
print m

Submission status: Wrong Answer

Solution code:
m=[]
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N:
    s=0
    for k in range(j,n):
      s+=A[k]
      B[j][k]=max(B[j][k],0)+s
    m=[max(B[j]+m)]
print m[0]

Submission status: Wrong Answer

Solution code:
m=-1e9
n=int(raw_input())
B=[[0]*(n+1) for _ in range(n+1)]
for _ in range(n):
  A=map(int,raw_input().split())
  for j in range(n):
    s=0
    for k in range(j,n):
      s+=A[k]
      B[j][k]=max(B[j][k],0)+s
    m=max(B[j]+[m])
print m

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098

"""
import sys
from sys import stdin
input = stdin.readline


def calc_points(n, array):
    # 右下から(x, y)までの長方形に含まれる値の和
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for y in range(n - 1, -1, -1):
        for x in range(n - 1, -1, -1):
            dp[y][x] = dp[y+1][x] + dp[y][x+1] - dp[y+1][x+1] + array[y][x]
    return dp


def solve(n, array):
    ans = []
    dp = calc_points(n, array)

    for sy in range(n + 1):
        for sx in range(n + 1):
            for ey in range(sy, n + 1):
                for ex in range(sx, n + 1):
                    s1 = dp[sy][sx] #  右下から始点まで
                    s2 = dp[sy][ex] #  重なり部分
                    s3 = dp[ey][sx] #  重なり部分
                    s4 = dp[ey][ex] #  重なりの重なり部分
                    s = s1 - s2 -s3 + s4 #  (sx, sy) - (ex, ey) 長方形の美味しさポイント
                    # area = abs(sy - ey) * abs(sx - ex) #  長方形の面積
                    ans.append(s)
    return max(ans)


def main(args):
    array = []
    # n = 3
    # array.append([1, -2, 3])
    # array.append([-4, 5, 6])
    # array.append([7, 8, -9])

    n = int(input())
    for _ in range(n):
        array.append([int(x) for x in input().split()])
    ans = solve(n, array)
    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
TLE n=85だと通らない
"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


def calc_points(n, array):
    # 右下から(x, y)までの長方形に含まれる値の和
    global dp
    for y in range(n - 1, -1, -1):
        for x in range(n - 1, -1, -1):
            dp[y][x] = dp[y+1][x] + dp[y][x+1] - dp[y+1][x+1] + array[y][x]


@lru_cache(maxsize=None)
def get_dp(y, x):
    return dp[y][x]


def solve(n, array):
    ans = 0
    calc_points(n, array)

    for sy in range(n + 1):
        for sx in range(n + 1):
            for ey in range(sy+1, n + 1):
                for ex in range(sx+1, n + 1):
                    s1 = get_dp(sy, sx)
                    s2 = get_dp(sy, ex)
                    s3 = get_dp(ey, sx)
                    s4 = get_dp(ey, ex)
                    s = s1 - s2 - s3 + s4
                    if s > ans:
                        ans = s
    return ans

dp = [[0] * (100 + 1) for _ in range(100 + 1)]
def main(args):
    array = []
    # n = 3
    # array.append([1, -2, 3])
    # array.append([-4, 5, 6])
    # array.append([7, 8, -9])

    n = int(input())
    for _ in range(n):
        array.append([int(x) for x in input().split()])
    ans = solve(n, array)
    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
def dfs(sq):
    if all([e==[] for e in sq]):
        return 0
    return max([sum([sum(e) for e in sq]),dfs([r[1:] for r in sq]),dfs([r[:-1] for r in sq]),dfs(sq[1:]),dfs(sq[:-1])])

print dfs([map(int,raw_input().split()) for u in xrange(input())])

Submission status: Wrong Answer

Solution code:
from itertools import permutations
n = input()
sq = [map(int,raw_input().split()) for u in xrange(n)]
s_sq =[[0]*(n+1) for u in xrange(n+1)]
ma = sq[0][0]
for i in xrange(n):
    for ii in xrange(n):
        s_sq[i][ii] = sq[i][ii] + s_sq[i][ii-1] + s_sq[i-1][ii] - s_sq[i-1][ii-1]
for tx,bx in permutations(range(n),2):
    for ty,by in permutations(range(n),2):
        #print "tx,ty=",tx,ty,"bx,by=",bx,by
        ma = max([ma,s_sq[by][bx]-s_sq[ty-1][bx]-s_sq[by][tx-1]+s_sq[ty-1][tx-1]])
print ma

Submission status: Wrong Answer

Solution code:
n = input()
sq = [map(int,raw_input().split()) for u in xrange(n)]
s_sq = [[[0]*n for u in xrange(n)] for uu in xrange(n)]
#s_sq[lower_end][left_end][right_end]
ma = 0
for y in xrange(n):
    temp = [0] * (n+1)
    for x in xrange(n):
        #make sum of the sequence left_end == 0, right_end == n
        temp[x] = temp[x-1] + sq[y][x]
    for tx in xrange(n):
        for ex in xrange(tx,n):
            s_sq[y][tx][ex] = max([0,s_sq[y-1][tx][ex]]) + temp[ex] - temp[tx-1]
            ma = max([ma,s_sq[y][tx][ex]])
print ma

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(0,n-m):
        s=sum(A[l][m:m+i+1])
        if s<0:continue
        for j in range(1,n-l):
            t=sum(A[l+j][m:m+i+1])
            if t<0:break
            s+=t
        if s>maxint:maxint=s
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
        t=maximum(A,i,j,n)
        if t>maxint:maxint=t
print maxint

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(0,n-m):
        s=sum(A[l][m:m+i+1])
        if s<0:continue
        for j in range(1,n-l):
            t=sum(A[l+j][m:m+i+1])
            if t<0:break
            s+=t
        if s>maxint:maxint=s
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
	t=maximum(A,i,j,n)
        if t>maxint:maxint=t
	t=maximum(A,j,i,n)
        if t>maxint:maxint=t
print maxint

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(0,n-m):
        s=sum(A[l][m:m+i+1])
        if s<0:continue
        for j in range(1,n-l):
            t=sum(A[l+j][m:m+i+1])
            if t<0:break
            s+=t
        if s>maxint:maxint=s
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
B=map(list,zip(*A))
maxint=A[0][0]
for i in range(n):
    for j in range(n):
	t=maximum(A,i,j,n)
	if t>maxint:maxint=t
	t=maximum(B,i,j,n)
	if t>maxint:maxint=t
print maxint

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(0,n-m):
        s=sum(A[l][m:m+i+1])
        #if s<0:continue                                                                
        for j in range(1,n-l):
            t=sum(A[l+j][m:m+i+1])
            if t<0:break
            s+=t
        if s>maxint:maxint=s
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
        t=maximum(A,i,j,n)
        if t>maxint:maxint=t
print maxint

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(m,n):
        s=sum(A[l][m:i+1])
        if i<>m and s<0:break
        if s<0:continue
        for j in range(l,n-1):
            t=sum(A[j+1][m:i+1])
            if t<0:break
            s+=t
	if s>maxint:maxint=s
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
        t=maximum(A,i,j,n)
        if t>maxint:maxint=t
print maxint

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(m,n):
        s=sum(A[l][m:i+1])
        if s<0:continue
        for j in range(l,n-1):
            t=sum(A[j+1][m:i+1])
            if t<=0:break
            s+=t
	if s>maxint:maxint=s
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
        t=maximum(A,i,j,n)
        if t>maxint:maxint=t
print maxint

Submission status: Wrong Answer

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(m,n):
        s=sum(A[l][m:i+1])
        if i<>m and s<0:break
        if s<0:continue
        for j in range(l,n-1):
            t=sum(A[j+1][m:i+1])
            if s+t<=0:break
            s+=t
            maxint=max(maxint,s)
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
        maxint=max(maximum(A,i,j,n),maxint)
print maxint

Submission status: Wrong Answer

Solution code:
import sys

n = int(raw_input())
cols = []
for row in sys.stdin:
    rows = map(int, row.split())
    cols.append(rows)

m = 0
for ci in xrange(n):
    for cj in xrange(n):
        for i in xrange(n-ci):
            for j in xrange(n-cj):
                s = 0 
                for si in xrange(i,i+ci+1):
                    for sj in xrange(j,j+cj+1):
                        s += cols[si][sj]
                if m < s:
                    m = s
print m

Submission status: Wrong Answer

Solution code:
import sys

n = int(raw_input())
cols = []
for row in sys.stdin:
    rows = map(int, row.split())
    cols.append(rows)

m = 0
for ci in xrange(n):
    for cj in xrange(n):
        for i in xrange(n-ci):
            for j in xrange(n-cj):
                #s = 0 
                s = []
                for si in xrange(i,i+ci+1):
                    for sj in xrange(j,j+cj+1):
                        #s += cols[si][sj]
                        s.append(cols[si][sj])
                if m < sum(s):
                    m = sum(s)
                #print s
print m

Submission status: Wrong Answer

Solution code:
def f(mtrx):
	maxSum = 0
	for rowStart in range(n):
		for  rowEnd in range(rowStart,n):
			for colStart in range(n):
				for colEnd in range(colStart,n):
					calcSum = 0
					for row in range(rowStart,rowEnd+1):
						calcSum += sum(mtrx[row][colStart:colEnd+1])
					maxSum = max(calcSum, maxSum)
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

Submission status: Wrong Answer

Solution code:
def x(a):
	m=-10**9
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			for r in N:
				p[r]+=a[r][e]
			m=max(P(p),m)
	return m

def P(a):
	m,c=-1000,0
	for i in N:
		c+=a[i]
		m=max(c,m)
		if c<0:c=0
	return m

n = input()
N = range(n)
print x([map(int, raw_input().split()) for i in N])

Submission status: Time Limit Exceeded

Solution code:
n=int(raw_input())
N=range(n)
N1=N+[n]
A=[[0]*(n+1)]+[[0]+map(int,raw_input().split()) for i in N]
B=[[0 for j in N1] for i in N1]
N1=N1[1:]
for i in N1:
  x=A[i]
  if i==0: y=[0]*n
  else: y=B[i-1][:]
  s=0
  for j in N1:
    s+=x[j]
    y[j]+=s
  B[i]=y
m=-1e6
for i1 in N1:
  for j1 in N1:
    for i2 in range(i1,n+1):
      for j2 in range(j1,n+1):
        m=max(m,B[i1-1][j1-1]+B[i2][j2]-B[i1-1][j2]-B[i2][j1-1])
print m

Submission status: Time Limit Exceeded

Solution code:
def f(i,j):
  B=[0]*n
  m=[]
  for x in range(i,n):
    a=0
    for y in range(j,n):
      a+=A[y][x]
      B[y]+=a
    m.append(max(B[j:]))
  return max(m)

n=int(raw_input())
N=range(n)
A=[map(int,raw_input().split()) for i in N]
print max([max([f(i,j) for i in N]) for j in N])

Submission status: Time Limit Exceeded

Solution code:
def g(j,i):
  a=B[j-1][i-1]
  m=[max([B[y][x]+a-B[y][i-1]-B[j-1][x] for y in range(j,n+1)]) for x in range(i,n+1)]
  return max(m)
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for j in N:
  A=map(int,raw_input().split())
  s=0
  for i in N:
    s+=A[i]
    B[j+1][i+1]=B[j][i+1]+s
N=N[1:]+[n]
m=[max([g(j,i) for i in N]) for j in N]
print max(m)

Submission status: Time Limit Exceeded

Solution code:
def g(j,i):
  a=B[j-1][i-1]
  b1=B[j-1]
  m=[]
  for y in range(j,n+1):
    b=B[y]
    m.append(max([b[x]+a-b[i-1]-b1[x] for x in range(i,n+1)]))
  return max(m)
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for j in N:
  A=map(int,raw_input().split())
  s=0
  b=B[j]
  for i in N:
    s+=A[i]
    B[j+1][i+1]=b[i+1]+s
N=N[1:]+[n]
m=[max([g(j,i) for i in N]) for j in N]
print max(m)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [[int(i) for i in input().split()] for j in range(n)]
m = -1000000000
for x1 in range(n):
  for x2 in range(x1,n):
    for y1 in range(n):
      for y2 in range(y1,n):
        s = 0
        for x in range(x1,x2+1):
          for y in range(y1,y2+1):
            s += l[y][x]
        if s > m:
          m = s
print(m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098

"""
import sys
from sys import stdin
input = stdin.readline


def calc_points(n, array):
    # 右下から(x, y)までの長方形に含まれる値の和
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for y in range(n - 1, -1, -1):
        for x in range(n - 1, -1, -1):
            dp[y][x] = dp[y+1][x] + dp[y][x+1] - dp[y+1][x+1] + array[y][x]
    return dp


def solve(n, array):
    ans = []
    dp = calc_points(n, array)

    for sy in range(n + 1):
        for sx in range(n + 1):
            for ey in range(sy+1, n + 1):
                for ex in range(sx+1, n + 1):
                    s1 = dp[sy][sx] #  右下から始点まで
                    s2 = dp[sy][ex] #  重なり部分
                    s3 = dp[ey][sx] #  重なり部分
                    s4 = dp[ey][ex] #  重なりの重なり部分
                    s = s1 - s2 -s3 + s4 #  (sx, sy) - (ex, ey) 長方形の美味しさポイント
                    # area = abs(sy - ey) * abs(sx - ex) #  長方形の面積
                    ans.append(s)
    return max(ans)


def main(args):
    array = []
    # n = 3
    # array.append([1, -2, 3])
    # array.append([-4, 5, 6])
    # array.append([7, 8, -9])

    n = int(input())
    for _ in range(n):
        array.append([int(x) for x in input().split()])
    ans = solve(n, array)
    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
TLE n=85だと通らない
"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


def calc_points(n, array):
    # 右下から(x, y)までの長方形に含まれる値の和
    global dp
    for y in range(n - 1, -1, -1):
        for x in range(n - 1, -1, -1):
            dp[y][x] = dp[y+1][x] + dp[y][x+1] - dp[y+1][x+1] + array[y][x]


# @lru_cache(maxsize=None)
def get_dp(y, x):
    return dp[y][x]


def solve(n, array):
    ans = float('-inf')
    calc_points(n, array)

    for sy in range(n + 1):
        for sx in range(n + 1):
            for ey in range(sy+1, n + 1):
                for ex in range(sx+1, n + 1):
                    s1 = get_dp(sy, sx)
                    s2 = get_dp(sy, ex)
                    s3 = get_dp(ey, sx)
                    s4 = get_dp(ey, ex)
                    s = s1 - s2 - s3 + s4
                    if s > ans:
                        ans = s
    return ans

dp = [[0] * (100 + 1) for _ in range(100 + 1)]
def main(args):
    array = []
    # n = 3
    # array.append([1, -2, 3])
    # array.append([-4, 5, 6])
    # array.append([7, 8, -9])

    n = int(input())
    for _ in range(n):
        array.append([int(x) for x in input().split()])
    ans = solve(n, array)
    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0098
TLE n=85だと通らない
"""
import sys
from sys import stdin
from functools import lru_cache
input = stdin.readline


def calc_points(n, array):
    # 右下から(x, y)までの長方形に含まれる値の和
    global dp
    for y in range(n - 1, -1, -1):
        for x in range(n - 1, -1, -1):
            dp[y][x] = dp[y+1][x] + dp[y][x+1] - dp[y+1][x+1] + array[y][x]


@lru_cache(maxsize=None)
def get_dp(y, x):
    return dp[y][x]


def solve(n, array):
    ans = float('-inf')
    calc_points(n, array)

    for sy in range(n + 1):
        for sx in range(n + 1):
            for ey in range(sy+1, n + 1):
                for ex in range(sx+1, n + 1):
                    s1 = get_dp(sy, sx)
                    s2 = get_dp(sy, ex)
                    s3 = get_dp(ey, sx)
                    s4 = get_dp(ey, ex)
                    s = s1 - s2 - s3 + s4
                    if s > ans:
                        ans = s
    return ans

dp = [[0] * (100 + 1) for _ in range(100 + 1)]
def main(args):
    array = []
    # n = 3
    # array.append([1, -2, 3])
    # array.append([-4, 5, 6])
    # array.append([7, 8, -9])

    n = int(input())
    for _ in range(n):
        array.append([int(x) for x in input().split()])
    ans = solve(n, array)
    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = [map(int, raw_input().split()) for i in range(n)]
dp = [[0 for j in range(n)] for i in range(n)]
ret = - (10 ** 10)

for i in range(n):
  for j in range(n):
    dp[i][j] += a[i][j]
    if i != 0: dp[i][j] += dp[i - 1][j]
    if j != 0: dp[i][j] += dp[i][j - 1]
    if i != 0 and j != 0: dp[i][j] -= dp[i - 1][j - 1]

for i in range(n):
  for j in range(n):
    for ii in range(i + 1):
      for jj in range(j + 1):
        t = dp[i][j]
        if ii != 0: t -= dp[ii - 1][j]
        if jj != 0: t -= dp[i][jj - 1]
        if ii != 0 and jj != 0: t += dp[ii - 1][jj - 1]
        ret = max(ret, t)

print ret

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement
n = input()
sq = [map(int,raw_input().split()) for u in xrange(n)]
s_sq =[[0]*(n+1) for u in xrange(n+1)]
ma = sq[0][0]
for i in xrange(n):
    for ii in xrange(n):
        s_sq[i][ii] = sq[i][ii] + s_sq[i][ii-1] + s_sq[i-1][ii] - s_sq[i-1][ii-1]
for tx,bx in combinations_with_replacement(range(n),2):
    for ty,by in combinations_with_replacement(range(n),2):
        #print "tx,ty=",tx,ty,"bx,by=",bx,by
        ma = max([ma,s_sq[by][bx]-s_sq[ty-1][bx]-s_sq[by][tx-1]+s_sq[ty-1][tx-1]])
print ma

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    aa = map(int, raw_input().split())
    for j in range(n):
        a[i + 1][j + 1] = a[i][j + 1] + a[i + 1][j] - a[i][j] + aa[j]
m = -10000 * 100 * 100
for i in range(n):
    for j in range(n):
        for k in range(i + 1, n + 1):
            for l in range(j + 1, n + 1):
                r = a[k][l] - a[k][j] - a[i][l] + a[i][j]
                m = max(m, r)
print m

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = [[0] * (n + 1) for _ in range(n + 1)]
for i in xrange(n):
    aa = map(int, raw_input().split())
    for j in range(n):
        a[i + 1][j + 1] = a[i][j + 1] + a[i + 1][j] - a[i][j] + aa[j]
m = -10000 * 100 * 100
for i in xrange(n):
    for j in xrange(n):
        for k in xrange(i + 1, n + 1):
            for l in xrange(j + 1, n + 1):
                r = a[k][l] - a[k][j] - a[i][l] + a[i][j]
                m = max(m, r)
print m

Submission status: Time Limit Exceeded

Solution code:
def f(mtrx):
	maxSum = -10**9
	for rowStart in range(n):
		for  rowEnd in range(rowStart,n):
			for colStart in range(n):
				for colEnd in range(colStart,n):
					calcSum = 0
					for row in range(rowStart,rowEnd+1):
						calcSum += sum(mtrx[row][colStart:colEnd+1])
					maxSum = max(calcSum, maxSum)
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

Submission status: Time Limit Exceeded

Solution code:
def f(mtrx):
	maxSum = -10000000
	partSum = [0]*n
	for colStart in range(n):
		for colEnd in range(colStart,n):
			for row in range(n):
				partSum[row] = sum(mtrx[row][colStart:colEnd+1])
			calcSum = maxPart(partSum)
			maxSum = max(calcSum, maxSum)
	return maxSum

def maxPart(mtrx):
	maxSum = -10000000
	for startP in range(n):
		for endP in range(startP,n):
			calcSum = sum(mtrx[startP:endP+1])
			maxSum = max(calcSum,maxSum)
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

Submission status: Time Limit Exceeded

Solution code:
def f(mtrx):
	maxSum = -10000000
	for colStart in range(n):
		partSum = [0]*n
		for colEnd in range(colStart,n):
			for row in range(n):
				partSum[row] += mtrx[row][colEnd]
			calcSum = maxPart(partSum)
			maxSum = max(calcSum, maxSum)
	return maxSum

def maxPart(mtrx):
	maxSum = -10000000
	for startP in range(n):
		for endP in range(startP,n):
			calcSum = sum(mtrx[startP:endP+1])
			maxSum = max(calcSum,maxSum)
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

Submission status: Accepted

Solution code:
m=-1e9
n=int(raw_input())
B=[[0]*(n+1) for _ in range(n+1)]
for _ in range(n):
  A=map(int,raw_input().split())
  for j in range(n):
    s=0
    for k in range(j,n):
      s+=A[k]
      B[j][k]=max(B[j][k],0)+s
      m=max(B[j][k],m)
print m

Submission status: Accepted

Solution code:
m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N:
    s=0
    for k in N[j:]:
      s+=A[k]
      B[j][k]=max(B[j][k],0)+s
      m=max(B[j][k],m)
print m

Submission status: Accepted

Solution code:
m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N:
    s=0
    b=B[j]
    for k in N[j:]:
      s+=A[k]
      b[k]=max(b[k],0)+s
      m=max(b[k],m)
print m

Submission status: Accepted

Solution code:
def f(m,b):
  s=0
  for k in N[j:]:
    s+=A[k]
    b[k]=max(b[k],0)+s
    m=max(b[k],m)
  return m,b

m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N: m,B[j]=f(m,B[j])
print m

Submission status: Accepted

Solution code:
n = int(input())

a = [list(map(int, input().split())) for i in range(n)]

# ?????????
sum_v = [[0 for i in range(n)] for i in range(n + 1)]
for i in range(n):
    c = 0
    for j in range(n):
        c += a[j][i]
        sum_v[j+1][i] = c

ans = -10**9


for sr in range(n):
    er = 0
    for er in range(sr, n):
        c = 0
        for col in range(n):
            c += sum_v[er+1][col] - sum_v[sr][col]
            ans = max(ans, c)
            if c < 0:
                c = 0  # c????????¢ (a(?????°) + b < b????????????

print(ans)

Submission status: Accepted

Solution code:
def x():
    m=-10**9
    for i in N:
        p=[0]*n
        for j in range(i,n):
            for k in N:
                p[k]+=l[k][j]
            m=max(P(p),m)
    return m

def P(a):
    m,c=-10**5,0
    for x in N:
        c+=a[x]
        m=max(c,m)
        if c<0:
            c=0
    return m


n=int(raw_input())
N=range(n)
l=[]
for i in N:
    l.append(map(int,raw_input().split()))
print x()

Submission status: Accepted

Solution code:
n = input()
a = [[0] * n] * n

for i in range(n):
    a[i] = map(int, raw_input().split())

ans = -1e100
for j1 in range(n):
    f = [0] * n
    for j2 in range(j1, n):
        for i in range(n):
            f[i] += a[i][j2]
        dp = [0] * n
        for i in range(n):
            if i == 0: dp[i] = f[i]
            else: dp[i] = max(f[i], f[i] + dp[i-1])
            ans = max(ans, dp[i])

print ans

Submission status: Accepted

Solution code:
n=int(input())
dp=[[0]*(n) for _ in range(n)]
ans=-10**9
a=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    s=[0]*101
    for j in range(n):s[j+1]=s[j]+a[i][j]
    for j in range(n):
        for k in range(j,n):
            dp[j][k]=max(dp[j][k],0)+s[k+1]-s[j]
            ans=max(ans,dp[j][k])
print(ans)

Submission status: Accepted

Solution code:
# AOJ 0098 Maximum Sum Sequence II 
# Python3 2018.6.17 bal4u


#include <stdio.h>

a = [[0 for c in range(102)] for r in range(102)]
s = [[0 for c in range(102)] for r in range(102)]

n = int(input())
for r in range(n):
	a[r] = list(map(int, input().split()))

for r in range(n):
	for c in range(n): s[r][c+1] += s[r][c]+a[r][c]

ans = s[0][1];
for c in range(n):
	for k in range(c+1, n+1):
		t = 0
		for r in range(n):
			if t < 0: t  = s[r][k]-s[r][c]
			else:     t += s[r][k]-s[r][c]
			if t > ans: ans = t

print(ans)

Submission status: Accepted

Solution code:
n = input()
sq = [map(int,raw_input().split()) for u in xrange(n)]
s_sq = [[[0]*n for u in xrange(n)] for uu in xrange(n)]
#s_sq[lower_end][left_end][right_end]
ma = -1000 * 100 * 100
for y in xrange(n):
    temp = [0] * (n+1)
    for x in xrange(n):
        #make sum of the sequence left_end == 0, right_end == n
        temp[x] = temp[x-1] + sq[y][x]
    for tx in xrange(n):
        for ex in xrange(tx,n):
            s_sq[y][tx][ex] = max([0,s_sq[y-1][tx][ex]]) + temp[ex] - temp[tx-1]
            ma = max([ma,s_sq[y][tx][ex]])
print ma

Submission status: Accepted

Solution code:
def maximum(A,l,m,n):
    maxint=A[l][m]
    for i in range(m,n):
        s=sum(A[l][m:i+1])
        if s<0:continue
        for j in range(l,n-1):
            t=sum(A[j+1][m:i+1])
            if s+t<=0:break
            s+=t
            maxint=max(maxint,s)
    return maxint

n=input()
A=[map(int,raw_input().split()) for i in range(n)]
maxint=A[0][0]
for i in range(n):
    for j in range(n):
        maxint=max(maximum(A,i,j,n),maxint)
print maxint

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit, maxsize


def find(n, data):
    temp = [0] * (n * (n+1) // 2)
    maximum = -maxsize

    for row in data:
        index = 0
        num_cell = 1

        for end in range(n, -1, -1):
            for i in range(end):
                k = index + i

                now = sum(row[i:i+num_cell])
                if temp[k] < 0:
                    temp[k] = now
                else:
                    temp[k] += now

                if maximum < temp[k]:
                    maximum = temp[k]

            index += end
            num_cell += 1

    return maximum


def main(readline=stdin.readline):
    n = int(readline())

    a = []
    for _ in range(n):
        a.append([int(s) for s in readline().split()])

    print(find(n, a))
    exit()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [[0] * (n + 1) for _ in range(n + 1)]
m = -10000 * 100 * 100

for i in range(n):
    b = map(int, raw_input().split())
    for j in range(n):
        aa = 0
        for k in range(j, n):
            aa += b[k]
            a[j][k] = max(a[j][k], 0) + aa
            m = max(m, a[j][k])
print m

Submission status: Accepted

Solution code:
def f(mtrx):
	maxSum = -10000000
	for colStart in range(n):
		partSum = [0]*n
		for colEnd in range(colStart,n):
			for row in range(n):
				partSum[row] += mtrx[row][colEnd]
			calcSum = maxPart(partSum)
			maxSum = max(calcSum, maxSum)
	return maxSum

def maxPart(array):
	maxSum = -10000000
	calcSum = 0
	for i in range(n):
		calcSum += array[i]
		maxSum = max(calcSum,maxSum)
		if calcSum < 0:
			calcSum = 0
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print f(mtrx)

Submission status: Accepted

Solution code:
def mx(mtrx):
	maxSum = -1000000
	for colStart in range(n):
		partSum = [0]*n
		for colEnd in range(colStart,n):
			for row in range(n):
				partSum[row] += mtrx[row][colEnd]
			maxSum = max(maxPart(partSum), maxSum)
	return maxSum

def maxPart(array):
	maxSum = -1000000
	calcSum = 0
	for i in range(n):
		calcSum += array[i]
		maxSum = max(calcSum,maxSum)
		if calcSum < 0:
			calcSum = 0
	return maxSum
	
n = int(raw_input())
mtrx = [map(int, raw_input().split()) for i in range(n)]
print mx(mtrx)

Submission status: Accepted

Solution code:
def mx(mtrx):
	maxSum = -1000000
	for colStart in range(n):
		partSum = [0]*n
		for colEnd in range(colStart,n):
			for row in range(n):
				partSum[row] += mtrx[row][colEnd]
			maxSum = max(maxPart(partSum), maxSum)
	return maxSum

def maxPart(array):
	maxSum = -1000000
	calcSum = 0
	for i in range(n):
		calcSum += array[i]
		maxSum = max(calcSum,maxSum)
		if calcSum < 0:	calcSum = 0
	return maxSum
	
n = int(raw_input())
print mx([map(int, raw_input().split()) for i in range(n)])

Submission status: Accepted

Solution code:
def x(a):
	m=-10**9
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			for r in N:
				p[r]+=a[r][e]
			m=max(P(p),m)
	return m

def P(a):
	m,c=-100000,0
	for i in N:
		c+=a[i]
		m=max(c,m)
		if c<0:c=0
	return m

n = input()
N = range(n)
print x([map(int, raw_input().split()) for i in N])

Submission status: Accepted

Solution code:
def x(a):
	m=-10**9
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			for r in N:
				p[r]+=a[r][e]
			m=max(P(p),m)
	return m
def P(a):
	m,c=-10**5,0
	for i in N:
		c+=a[i]
		m=max(c,m)
		if c<0:c=0
	return m
n = input()
N = range(n)
print x([map(int, raw_input().split()) for i in N])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N = int(readline())
    A = [list(map(int, readline().split())) for i in range(N)]
    B = [[0]*(N+1) for i in range(N+1)]
    for i in range(N):
        c = 0
        Ai = A[i]
        Bi = B[i]
        Bj = B[i+1]
        for j in range(N):
            Bj[j+1] = Bi[j+1] + Ai[j]
    def gen():
        for i0 in range(N):
            Ba = B[i0]
            for i1 in range(i0+1, N+1):
                Bb = B[i1]
                mi = su = 0
                for j in range(N):
                    su += Bb[j+1] - Ba[j+1]
                    yield su - mi
                    mi = min(mi, su)
    write("%d\n" % max(gen()))
solve()