Problem:


最短経路

図１に例示するように整数（0 以上 99 以下）をひしがたに並べます。このような、ひしがたを表すデータを読み込んで、一番上からスタートして一番下まで次のルールに従って進むとき、通過する整数の和の最大値を出力するプログラムを作成してください。

各ステップで、対角線上の左下か対角線上の右下に進むことができます。

例えば図1の例では、図2に示すように、7,3,8,7,5,7,8,3,7を選んで通ったとき、その和は最大の 55 （7+3+8+7+5+7+8+3+7=55） となります。

Input

入力例に示すように、カンマで区切られた整数の並びが、ひし形状に与えられます。各行に空白文字は含まれません。入力例は図１に対応しています。
データの行数は 100 行未満です。

Output

ルールに従って通過する整数の和の最大値を１行に出力します。

Sample Input

7
3,8
8,1,0
2,7,4,4
4,5,2,6,5
2,7,4,4
8,1,0
3,8
7

Sample Output

55



Sample input:
7
3,8
8,1,0
2,7,4,4
4,5,2,6,5
2,7,4,4
8,1,0
3,8
7


Sample output:
55

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

Submission status: Wrong Answer

Solution code:
import sys
def index(x,n):
    if x < 0: return 0
    if n < x: return n
    return x

las = map(int,raw_input())
for s in sys.stdin:
    now = map(int,s.split(","))
    nin,lin = len(now)-1,len(las)-1
    d = -1
    if nin > lin: d = -1
    if nin < lin: d = 1
    for i in xrange(nin+1):
        now[i] += max(
        las[index(i+d,lin)],
        las[index(i,lin)]
        )
    if not nin: print now[0]
    las = now

Submission status: Wrong Answer

Solution code:
g=[[] for _ in xrange(100)]
i=-1
while 1:
    i+=1
    try:
        g[i]=map(int,raw_input().split(","))
    except:
        dp=[[0]*101 for _ in xrange(101)]
        dp[0][0]=7
        for j in xrange(1,i):
            for k in xrange(len(g[j])):
                if j<=i/2:
                    dp[j][k]=max(dp[j-1][k-1],dp[j-1][k])+g[j][k]
                else:
                    dp[j][k]=max(dp[j-1][k],dp[j-1][k+1])+g[j][k]
        print(dp[i-1][0])
        break

Submission status: Wrong Answer

Solution code:
path=[]
while(True):
    try:
        temp=list(map(int,input().split(',')))
        path.append(temp)
    except:
        break

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 for j in range(len(s[i])):
  t=j-len(s[i])>len(s[i-1])
  s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Wrong Answer

Solution code:
def dmax(l):
  for k in range(len(l)-1):
    for (i,j) in enumerate(l[k]):
      l[k+1].insert(2*i+1,j)
    l[k+1]=[l[k+1][i+1]+j for (i,j) in enumerate(l[k+1][:-1])]
    o=l[k+1][1:-1]
    l[k+1]=[l[k+1][0]]+[o[i] if o[i]>=o[i+1] else o[i+1] for i in range(0,len(o),2)]+[l[k+1][-1]]
  return max(l[-1])

cnt=0
l=[]
while 1:
  t=list(map(int,input().split(",")))
  l.extend([t])
  if len(t)==1 and cnt>0:break
  cnt+=1
b=len(l)//2+1
m=dmax(l[:b])+dmax(l[b:][::-1])

Submission status: Wrong Answer

Solution code:
def path(w,h,sm):
	global mx
	if w < 0 or len(inp[h])-1 < w: return 0
	sm += inp[h][w]
	if sm < mx[h][w]: return 0
	else: mx[h][w] = sm
	if h == c-1: return sm
	if h < c/2:	return max(path(w,h+1,sm),path(w+1,h+1,sm))
	else: return max(path(w,h+1,sm),path(w-1,h+1,sm))
		
c = 0
inp = []
while True:
	try:
		inp.append(map(int, raw_input().split(",")))
		c += 1
	except:
		mx = [[0 for i in range((c+1)/2)] for i in range(c)]
		print path(0,0,0)
		print mx
		break

Submission status: Wrong Answer

Solution code:
def path(mx,w,h):
	if h < c/2:
		if w > 0:
			mx[h][w] = max(mx[h-1][w],mx[h-1][w-1]) + inp[h][w]
		else:
			mx[h][w] = mx[h-1][w] + inp[h][w]
	else:
		if w < len(inp[h])-1:
			mx[h][w] = max(mx[h-1][w],mx[h-1][w+1]) + inp[h][w]
		else:
			mx[h][w] = mx[h-1][w] + inp[h][w]
	return mx
	
c = 0
inp = []
while True:
	try:
		inp.append(map(int, raw_input().split(",")))
		c += 1
	except:
		mx = [[0 for i in range((c+1)/2)] for i in range(c)]
		mx[0][0] = inp[0][0]
		for h in range(1,c):
			for w in range(len(inp[h])):
				mx = path(mx,w,h)
		print mx[c-1][0]
		break

Submission status: Wrong Answer

Solution code:
def path(mx,w,h):
	i = -1 if h < c/2 else 1
	if (i == -1 and w > 0) or (i == 1 and w < len(inp[h])-1):
		mx[h][w] = max(mx[h-1][w],mx[h-1][w+i]) + inp[h][w]
	else:
		mx[h][w] = mx[h-1][w] + inp[h][w]
	return mx
	
c = 0
inp = []
while True:
	try:
		inp.append(map(int, raw_input().split(",")))
		c += 1
	except:
		break
mx = [[0 for i in range((c+1)/2)] for i in range(c)]
mx[0][0] = inp[0][0]
for h in range(1,c):
	for w in range(len(inp[h])):
		mx = path(mx,w,h)
print mx[c-1][0]

Submission status: Time Limit Exceeded

Solution code:
count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    if dp_[i][j]:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    if dp_[i][j]:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    global dp_
    if dp_[i][j]:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        count += 1
        a.append([int(i) for i in input().split(",")])
    except EOFError:
        break
dim = int(count/2)
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    global dp_
    if dp_[i][j]:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
    return dp_[i][j]

print(dp(0,0))

Submission status: Time Limit Exceeded

Solution code:
#-*- coding: utf_8 -*-

data = []
data.append([int(input())])
length = 2
while length != 1:
    r = [int(x) for x in input().split(",")]
    data.append(r)
    length = len(r)

first = data[:int(len(data)/2) + 1]
mx_arr = [0] * 100

def dfs(n, i, mx):
    if n == len(first) - 1:
        s = mx * 2 + data[n][i]
        mx_arr[i] = max(s, mx_arr[i])
        return

    mx += data[n][i]
    dfs(n + 1, i, mx)
    dfs(n + 1, i + 1, mx)

dfs(0, 0, 0)

print(max(mx_arr))

Submission status: Time Limit Exceeded

Solution code:
def path(w,h,sm):
	if w < 0 or len(inp[h])-1 < w: return 0
	sm += inp[h][w]
	if h == c-1: return sm
	if h < c/2:	return max(path(w,h+1,sm),path(w+1,h+1,sm))
	else: return max(path(w,h+1,sm),path(w-1,h+1,sm))
		
c = 0
inp = []
while True:
	try:
		inp.append(map(int, raw_input().split(",")))
		c += 1
	except:
		print path(0,0,0)
		break

Submission status: Accepted

Solution code:
from copy import copy
import sys
sys.setrecursionlimit(1000000)

count = 0
a = []
while(1):
    try:
        a.append([int(i) for i in input().split(",")])
        count += 1
    except EOFError:
        break
dim = int(count/2)+1
b = [[0 for i in range(dim+1)] for j in range(dim+1)]
for i in range(dim):
    for j in range(i+1):
        b[i-j][j] = a[i][j]
for i in range(dim-1):
    for j in range(dim-i-1):
        b[dim-1-j][i+1+j] = a[i+dim][j]

dp_ = [[True if i < dim else 0 for i in range(dim+1)] if j < dim else [0 for i in range(dim+1)] for j in range(dim+1)]

def dp(i,j):
    global dp_
    if dp_[i][j] is True:
        dp_[i][j] = b[i][j] + max(dp(i+1,j),dp(i,j+1))
        return dp_[i][j]
    else:
        return dp_[i][j]

print(dp(0,0))

Submission status: Accepted

Solution code:
import sys
def index(x,n):
    if x < 0: return 0
    if n < x: return n
    return x

las = [int(raw_input())]
for s in sys.stdin:
    now = map(int,s.split(","))
    nin,lin = len(now)-1,len(las)-1
    if nin > lin: d = -1
    if nin < lin: d = 1
    for i in xrange(nin+1):
        now[i] += max(las[index(i+d,lin)],las[index(i,lin)])
    if not nin: print now[0]
    las = now

Submission status: Accepted

Solution code:
import sys
f = sys.stdin


lines = [list(map(int,line.split(','))) for line in f]

for i in range(1, len(lines) // 2 + 1):
    for j in range(len(lines[i])):
        lines[i][j] += max(lines[i - 1][max(j - 1,0):min(j + 1,len(lines[i -1]) )])

for i in range(len(lines) // 2 + 1, len(lines)):
    for j in range(len(lines[i])):
        lines[i][j] += max(lines[i - 1][j:j +2])

print(lines[-1][0])

Submission status: Accepted

Solution code:
def mx(p,w,h,l):
    if h<=c/2:
        if w==0:
            p[h][w]+=p[h-1][w]
        elif w==l-1:
            p[h][w]+=p[h-1][w-1]
        else:
            p[h][w]+=max(p[h-1][w],p[h-1][w-1])
    else:
        p[h][w]+=max(p[h-1][w],p[h-1][w+1])
    return p
c=0
p=[]
while 1:
    try:
        p.append(map(int, raw_input().split(',')))
        c+=1
    except:
        break

for h in range(1,c):
    l=len(p[h])
    for w in range(l):
        p=mx(p,w,h,l)
print p[c-1][0]

Submission status: Accepted

Solution code:
g=[[] for _ in xrange(100)]
i=-1
while 1:
    i+=1
    try:
        g[i]=map(int,raw_input().split(","))
    except:
        dp=[[0]*101 for _ in xrange(101)]
        dp[0][0]=g[0][0]
        for j in xrange(1,i):
            for k in xrange(len(g[j])):
                if j<=i/2:
                    dp[j][k]=max(dp[j-1][k-1],dp[j-1][k])+g[j][k]
                else:
                    dp[j][k]=max(dp[j-1][k],dp[j-1][k+1])+g[j][k]
        print(dp[i-1][0])
        break

Submission status: Accepted

Solution code:
#-*- coding: utf_8 -*-

data = []
data.append([int(input())])
length = 2
counter = 0
while length != 1:
    r = [int(x) for x in input().split(",")]
    data.append(r)
    length = len(r)
    counter += 1

N = int((counter + 1 )/ 2) + 1
dp = [[0 for i in range(N)] for j in range(N)]
data_arr = [[0 for i in range(N)] for j in range(N)]

left = data[:N]
right = data[N:]

i = 0
for v in left:
    for idx, r in enumerate(v):
        data_arr[i - idx][idx] = r
    i += 1
right.reverse()
for i, v in enumerate(right):
    for idx, r in enumerate(v):
        data_arr[N - 1 - idx][N - 1 - i + idx] = r


dp[0][0] = data_arr[0][0]

for i in range(1, N):
    dp[0][i] = dp[0][i - 1] + data_arr[0][i]
    dp[i][0] = dp[i - 1][0] + data_arr[i][0]

for i in range(1, N):
    for j in range(1, N):
        dp[i][j] += data_arr[i][j] + max(dp[i - 1][j], dp[i][j - 1])

print(dp[N - 1][N - 1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

def print_square(A):
    print('---')
    for row in A:
        print(row)

# input square
A = []
for s in sys.stdin:
    lst = list(map(int, s.split(',')))
    A.append(lst)

# accumulated sum square
S = []
for a in A:
    S.append([None] * len(a))

S[0][0] = A[0][0]
for i in range(1, len(A) // 2 + 1):
    for j in range(len(A[i])):
        if j == 0:
            S[i][j] = S[i - 1][j] + A[i][j]
        elif j == len(A[i]) - 1:
            S[i][j] = S[i - 1][j - 1] + A[i][j]
        else:
            S[i][j] = max(S[i-1][j-1] + A[i][j], S[i-1][j] + A[i][j])

for i in range(len(A) // 2 + 1, len(A)):
    for j in range(len(A[i])):
        left = S[i - 1][j]
        right = S[i - 1][j + 1]
        S[i][j] = max(left, right) + A[i][j]

print(S[-1][0])

Submission status: Accepted

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


def solve(data):
    increasing = True
    prev_line = data[0]
    for curr_line in data[1:]:
        if len(curr_line) < len(prev_line):
            increasing = False
        for i, ele in enumerate(curr_line):
            if increasing:
                if i == 0:
                    curr_line[0] += prev_line[0]
                else:
                    try:
                        up_right = prev_line[i]
                    except:
                        up_right = 0
                    curr_line[i] += max(prev_line[i-1], up_right)
            else:
                    curr_line[i] += max(prev_line[i], prev_line[i+1])
        prev_line = curr_line
    return data[-1][0]


def main(args):
    data = []
#    data.append([7])
#    data.append([3,8])
#    data.append([8,1,0])
#    data.append([2,7,4,4])
#    data.append([4,5,2,6,5])
#    data.append([2,7,4,4])
#    data.append([8,1,0])
#    data.append([3,8])
#    data.append([7])

    for line in sys.stdin:
        data.append([int(x) for x in line.split(',')])
    result = solve(data)
    print(result)



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

Submission status: Accepted

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


def solve(data):
    """
    ??????????????????????????????????????§????????????????????????????????????
    (2????????\??????)??????????´????????????????????????????????????????????????????????´???????????????°?????§????????????
    ????????????????????????????????§???????????????????????????????????°?????????????????????????????§???????????????
    ????????????????????§??°???????????°??????????????????????????????
    :param data: ??±??¢?????\????????????
    :return: ?????§???????????£?????????????¨????
    """
    increasing = True           #  ??±??¢????¨????????¢???????????????£??????????????????????????????????????°
    prev_line = data[0]
    for curr_line in data[1:]:
        if len(curr_line) < len(prev_line):
            increasing = False
        for i, ele in enumerate(curr_line):
            if increasing:
                try:
                    up_left = prev_line[max(0, i-1)] #  prev_line[-1]?????¨?????????????????£?????????????????§???index???????????°??????????????????????????????
                except:
                    up_left = 0
                try:
                    up_right = prev_line[i]
                except:
                        up_right = 0
                curr_line[i] += max(up_left, up_right)
            else:               #  ??±??¢????¨???????????????§???????????????????????????[i], [i+1]??????????????¨???????????§?????\??????????????????
                    curr_line[i] += max(prev_line[i], prev_line[i+1])
        prev_line = curr_line
    return data[-1][0]


def main(args):
    data = []
#    data.append([7])
#    data.append([3,8])
#    data.append([8,1,0])
#    data.append([2,7,4,4])
#    data.append([4,5,2,6,5])
#    data.append([2,7,4,4])
#    data.append([8,1,0])
#    data.append([3,8])
#    data.append([7])

    for line in sys.stdin:
        data.append([int(x) for x in line.split(',')])
    result = solve(data)
    print(result)


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

Submission status: Accepted

Solution code:
# Aizu Problem 0089: The Shortest Path on A Rhombic Path
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


rhombic = [[int(_) for _ in line.split(',')] for line in sys.stdin]
n = len(rhombic)
sums = [rhombic[0][0]]
for k in range(1, n // 2 + 1):
    row = [sums[0] + rhombic[k][0]]
    for i in range(1, len(rhombic[k-1])):
        row.append(rhombic[k][i] + max(sums[i-1], sums[i]))                
    row.append(sums[-1] + rhombic[k][-1])
    sums = row[:]
for k in range(n // 2 + 1, n):
    row = []
    for i in range(len(rhombic[k])):
        row.append(rhombic[k][i] + max(sums[i], sums[i+1]))                
    sums = row[:]
print(sums[0])

Submission status: Accepted

Solution code:
INF=1e8
path=[]
dp=[]
while(True):
    try:
        temp=list(map(int,input().split(',')))
        path.append(temp)
        dp.append([INF for i in range(len(temp))])
    except:
        break
dp[0][0]=path[0][0]
for i in range(1,len(dp)):
    for j in range(len(dp[i])):
        if len(dp[i])>len(dp[i-1]):
            start=0 if j-1<0 else j-1
            dp[i][j]=max(dp[i-1][start:j+1])+path[i][j]
        else:
            dp[i][j]=max(dp[i-1][j:j+2])+path[i][j]
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

table = [[0 for i in range(100)] for j in range(100)]
L = list(get_input())
N = len(L) // 2 + 1

for l in range(N):
    points = [int(i) for i in L[l].split(",")]
    for i in range(len(points)):
        table[len(points)-i-1][i] = points[i]

for l in range(N, 2*N-1):
    #print(l)
    points = [int(i) for i in L[l].split(",")]
    for i in range(len(points)):
        #print(len(points)-i-1+(l-N+1),i+(l-N+1))
        table[len(points)-i-1+(l-N+1)][i+(l-N+1)] = points[i]


for c in range(1,2*N):
    for i in range(c):
        if c-i-2 < 0:
            table[c-i-1][i] += table[c-i-1][i-1]
        elif i-1 < 0:
            table[c-i-1][i] += table[c-i-2][i]
        else:
            table[c-i-1][i] += max(table[c-i-2][i], table[c-i-1][i-1])

#for i in range(N):
#    for j in range(N):
#        print(table[i][j], end=" ")
#    print("")

print(table[N-1][N-1])

Submission status: Accepted

Solution code:
ans = [int(input())]
while True:
    try:
        inp = list(map(int, input().split(",")))
        l = len(inp)
        if l > len(ans):
            tmp = [-float("inf")] + ans + [-float("inf")]
        else:
            tmp = ans
        ans = []
        for i in range(l):
            ans.append(max([tmp[i] + inp[i], tmp[i + 1] + inp[i]]))
    except:
        break
print(*ans)

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)//2+1):
    for j in range(len(s[i])):
        s[i][j] += max(s[i-1][max(j-1,0):min(j+1,len(s[i-1]))])
for i in range(len(s)//2+1,len(s)):
    for j in range(len(s[i])):
        s[i][j] += max(s[i-1][j:j+2])
print(s[-1][0])

Submission status: Accepted

Solution code:
ans = [int(input())]
import sys
for e in sys.stdin:
    inp = list(map(int, e.split(",")))
    l = len(inp)
    if l > len(ans):
        tmp = [-float("inf")] + ans + [-float("inf")]
    else:
        tmp = ans
    ans = []
    for i in range(l):
        ans += [max([tmp[i] + inp[i], tmp[i + 1] + inp[i]])]
print(*ans)

Submission status: Accepted

Solution code:
path=[]
while(True):
    try:
        temp=list(map(int,input().split(',')))
        path.append(temp)
    except:
        break
path[0][0]
for i in range(1,len(path)):
    for j in range(len(path[i])):
        if len(path[i])>len(path[i-1]):
            start=0 if j<1 else j-1
            path[i][j]+=max(path[i-1][start:j+1])
        else:
            path[i][j]+=max(path[i-1][j:j+2])
print(path[-1][-1])

Submission status: Accepted

Solution code:
import sys
path=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(path)):
    for j in range(len(path[i])):
        if len(path[i])>len(path[i-1]):
            start=0 if j<1 else j-1
            path[i][j]+=max(path[i-1][start:j+1])
        else:
            path[i][j]+=max(path[i-1][j:j+2])
print(path[-1][-1])

Submission status: Accepted

Solution code:
import sys
path=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(path)):
    for j in range(len(path[i])):
        if len(path[i])>len(path[i-1]):
            start=0 if j<1 else j-1
            path[i][j]+=max(path[i-1][~-j*(j>0):j+1])
        else:
            path[i][j]+=max(path[i-1][j:j+2])
print(path[-1][-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 for j in range(len(s[i])):
  b=len(s[i])>len(s[i-1])
  s[i][j]+=max(s[i-1][(j-b)*(j>0):j+2-b])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 for j in range(len(s[i])):
  t=j-(len(s[i])>len(s[i-1]))
  s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k=len(s[i])
 for j in range(k):
  t=j-(k>len(s[i-1]))
  s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k,a=len(s[i]),s[i-1]
 for j in range(k):
  t=j-(k>len(a))
  s[i][j]+=max(a[t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k=len(s[i])
 b=k>len(s[i-1])
 for j in range(k):
  t=j-b
  s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k=len(s[i]);b=k>len(s[i-1])
 for j in range(k):
  t=j-b
  s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k=len(s[i]);b=k>len(s[i-1])
 for j in range(k):
  t=j-b;s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k=len(s[i]);b=k>len(s[i-1])
 for j in range(k):t=j-b;s[i][j]+=max(s[i-1][t*(j>0):t+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k=len(s[i]);b=k>len(s[i-1])
 for j in range(k):s[i][j]+=max(s[i-1][(j-b)*(j>0):j-b+2])
print(*s[-1])

Submission status: Accepted

Solution code:
import sys
s=[list(map(int,e.split(',')))for e in sys.stdin]
for i in range(1,len(s)):
 k,l=s[i-1],len(s[i]);b=l>len(k)
 for j in range(l):s[i][j]+=max(k[(j-b)*(j>0):j-b+2])
print(*s[-1])

Submission status: Accepted

Solution code:
mp = []
while True:
  try:
    lst = list(map(int, input().split(",")))
    mp.append(lst)
  except EOFError:
    break

half = len(mp) // 2

for i in range(1, len(mp)):
  for j in range(len(mp[i])):
    if i <= half:
      if j != 0 and j != len(mp[i]) - 1:
        mp[i][j] = max(mp[i - 1][j], mp[i - 1][j - 1]) + mp[i][j]
      elif j == 0:
        mp[i][j] = mp[i - 1][j] + mp[i][j]
      else:
        mp[i][j] = mp[i - 1][j - 1] + mp[i][j]

    else:
      mp[i][j] = max(mp[i - 1][j], mp[i - 1][j + 1]) + mp[i][j]

print(mp[-1][0])

Submission status: Accepted

Solution code:
# AOJ 0089 The Shortest Path on A Rhombic Path
# Python3 2018.6.21 bal4u

s = [[0 for i in range(100)] for j in range(100)]
w = k = 0
while 1:
	try: a = list(map(int, input().split(',')))
	except: break
	n = len(a)
	if n > w:
		w = n
		s[k+1][0] = s[k][0] + a[0]
		for i in range(1, n): s[k+1][i] = max(s[k][i-1], s[k][i]) + a[i]
		s[k+1][n-1] = s[k][n-2] + a[n-1]
	else:
		for i in range(n): s[k+1][i] = max(s[k][i], s[k][i+1]) + a[i]
	k += 1
print(s[k][0])

Submission status: Accepted

Solution code:
import sys
dp=[[0]*52 for unused in xrange(100)]
dia=[map(int,line.strip().split(",")) for line in sys.stdin.readlines()]
dp[0][0]=dia[0][0]
for i in xrange(1,len(dia)/2):
    for j in xrange(len(dia[i])):
        #dp[0][-1]==dp[0][51]==0
        dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+dia[i][j]
for i in xrange(len(dia)/2,len(dia)):
    for j in xrange(len(dia[i])):
        dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+dia[i][j]
print dp[len(dia)-1][0]

Submission status: Accepted

Solution code:
def wa(L,cnt):
    for i in range(1,cnt/2+1):
        L[i][0]+=L[i-1][0]
        for j in range(1,len(L[i])-1):
            L[i][j]+=max(L[i-1][j-1],L[i-1][j])
        j=len(L[i])-1
        L[i][j]+=L[i-1][j-1]
L=[]
cnt=0
while True:
    try:
        L.append(map(int,raw_input().split(",")))
        cnt+=1
    except EOFError:
        break

wa(L,cnt)
wa(L[::-1],cnt)
print max(L[cnt/2])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin


def solve(L, num_rows, level, up):
    if level >= num_rows:
        return
    next_ = L[level]
    prev = L[level-1]
    if up:
        for i in range(len(next_)):
            next_[i] += max(prev[max(0, i-1):i+1])
    else:
        for i in range(len(next_)):
            next_[i] += max(prev[i:i+2])
    solve(L, num_rows, level+1, num_rows // 2 > level)

L = []
for line in stdin:
    L.append([int(s) for s in line.split(',')])

solve(L, len(L), 1, True)
print(L[-1][0])

Submission status: Accepted

Solution code:
def path(w,h,sm):
	global mx
	if w < 0 or len(inp[h])-1 < w: return 0
	sm += inp[h][w]
	if sm < mx[h][w]: return 0
	else: mx[h][w] = sm
	if h == c-1: return sm
	if h < c/2:	return max(path(w,h+1,sm),path(w+1,h+1,sm))
	else: return max(path(w,h+1,sm),path(w-1,h+1,sm))
		
c = 0
inp = []
while True:
	try:
		inp.append(map(int, raw_input().split(",")))
		c += 1
	except:
		mx = [[0 for i in range((c+1)/2)] for i in range(c)]
		print path(0,0,0)
		break

Submission status: Accepted

Solution code:
def mx(inp,w,h):
	if h <= c/2:
		if w == 0: inp[h][w] += inp[h-1][w]
		elif w == len(inp[h])-1: inp[h][w] += inp[h-1][w-1]
		else: inp[h][w] += max(inp[h-1][w],inp[h-1][w-1])
	else:
		inp[h][w] += max(inp[h-1][w],inp[h-1][w+1])
	return inp

c = 0
inp = []
while True:
	try:
		inp.append(map(int, raw_input().split(",")))
		c += 1
	except:
		break
	
for h in range(1,c):
	for w in range(len(inp[h])):
		inp = mx(inp,w,h)
print inp[c-1][0]

Submission status: Accepted

Solution code:
def mx(p,w,h,l):
	if h <= c/2:
		if w == 0: p[h][w] += p[h-1][w]
		elif w == l-1: p[h][w] += p[h-1][w-1]
		else: p[h][w] += max(p[h-1][w],p[h-1][w-1])
	else:
		p[h][w] += max(p[h-1][w],p[h-1][w+1])
	return p

c = 0
p = []
while True:
	try:
		p.append(map(int, raw_input().split(",")))
		c += 1
	except:
		break
	
for h in range(1,c):
	l = len(p[h])
	for w in range(l):
		p = mx(p,w,h,l)
print p[c-1][0]

Submission status: Accepted

Solution code:
nl = []; c = 0;
INF = 10**9+7; ans = 0;
while True:
    try:
        l = map(int, raw_input().split(','))
        nl.append(l)
        c += 1
    except EOFError:
        break
cn = (c + 1)/2
dp1, dp2 = [0], [0]
for i in xrange(1,cn):
    dp1 = [ max(dp1[j-1]+nl[i-1][j-1] if j>0 else 0, dp1[j]+nl[i-1][j] if j<i else 0) for j in xrange(i+1)]
for i in xrange(1,cn):
    dp2 = [ max(dp2[j-1]+nl[c-i][j-1] if j>0 else 0, dp2[j]+nl[c-i][j] if j<i else 0) for j in xrange(i+1)]
for i in xrange(cn):
    ans = max(ans, dp1[i] + dp2[i] + nl[cn-1][i])
print ans

Submission status: Accepted

Solution code:
import sys
x=[]
for s in sys.stdin:
  A=map(int,s[:-1].split(','))
  n=len(A)
  if len(x)<n: x=[0]+x+[0]
  x=[max(x[i:i+2])+A[i] for i in range(n)]
print x[0]

Submission status: Accepted

Solution code:
import sys
x=[]
for s in sys.stdin:
  A=map(int,s[:-1].split(','))
  n=len(A)
  if len(x)<n:x=[0]+x+[0]
  x=[max(x[i:i+2])+A[i] for i in range(n)]
print x[0]

Submission status: Accepted

Solution code:
diamond=[]
path=[]
while True:
    try:
        s=[int(i) for i in input().split(",")]
        if(len(diamond)==0):
            diamond.append(s)
            path.append(s)
        elif(len(diamond[-1])<len(s)):
            diamond.append(s)
            _path=[path[-1][0]+s[0]]
            for i in range(len(s)-2):
                _path.append(max(path[-1][i],path[-1][i+1])+s[i+1])
            _path.append(path[-1][-1]+s[-1])
            path.append(_path)

        else:
            diamond.append(s)
            _path=[]
            for i in range(len(s)):
                _path.append(max(path[-1][i],path[-1][i+1])+s[i])
            path.append(_path)

            if len(s)==1:
                print(path[-1][0])
                diamond=[]
                path=[]
    except EOFError:
        break

Submission status: Accepted

Solution code:
while 1:
    try:
        count = 0
        rom = []
        while count != 2:
            N = list(map(int, input().split(",")))
            if len(N) == 1:
                count += 1
            rom.append(N)
        half = len(rom) // 2

        for i in range(1, len(rom)):
            for j in range(len(rom[i])):
                if i <= half:
                    if j != 0 and j != len(rom[i]) - 1:
                        rom[i][j] = max(rom[i - 1][j], rom[i - 1][j - 1]) + rom[i][j]
                    elif j == 0:
                        rom[i][j] = rom[i - 1][j] + rom[i][j]
                    else:
                        rom[i][j] = rom[i - 1][j - 1] + rom[i][j]
                else:
                    rom[i][j] = max(rom[i - 1][j], rom[i - 1][j + 1]) + rom[i][j]

        print(rom[-1][0])
    except:
        break

Submission status: Accepted

Solution code:
import sys
a = [list(map(int, l.split(","))) for l in sys.stdin]
dp = a[0]

for i in range(1, (len(a)+1)//2):
    _dp = [0]*(i+1)
    for j in range(i):
        _dp[j] = max(_dp[j], dp[j]+a[i][j])
        _dp[j+1] = max(_dp[j+1], dp[j]+a[i][j+1])
    dp = _dp

for i in range((len(a)+1)//2, len(a)):
    _dp = [0]*(len(dp)-1)
    for j in range(len(_dp)):
        _dp[j] = max(dp[j], dp[j+1]) + a[i][j]
    dp = _dp

print(dp[0])

Submission status: Runtime Error

Solution code:
import sys
def index(x,n):
    if x < 0: return 0
    if n < x: return n
    return x

las = map(int,raw_input())
for s in sys.stdin:
    now = map(int,s.split(","))
    nin,lin = len(now)-1,len(las)-1
    if nin > lin: d = -1
    if nin < lin: d = 1
    for i in xrange(nin+1):
        now[i] += max(las[index(i+d,lin)],las[index(i,lin)])
    if not nin: print now[0]
    las = now

Submission status: Runtime Error

Solution code:
def mx(p,w,h,l):
	if h <= c/2:
		if w == 0: p[h][w] += p[h-1][w]
		elif w == l-1: p[h][w] += p[h-1][w-1]
		else: p[h][w] += max(p[h-1][w],p[h-1][w-1])
	else:
		p[h][w] += max(p[h-1][w],p[h-1][w+1])
	return p

c = 0
p = []
while True:
	try:
		p.append(map(int, raw_put().split(",")))
		c += 1
	except:
		break
	
for h in range(1,c):
	l = len(p[h])
	for w in range(l):
		p = mx(p,w,h,l)
print p[c-1][0]