1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
from types import GeneratorType
from typing import TypeVar, List, Dict, Any, Callable
class SA:
def __init__(self, x, y):
self.x = x
self.y = y
def __lt__(self, other):
return self.x < other.x
N = int(20)
M = int(20)
INF = int(2e9)
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n")
read = lambda: map(int, input().split())
read_list = lambda: list(map(int, input().split()))
class std:
@staticmethod
def bootstrap(f, stack=None):
if stack is None:
stack = []
def wrappedfunc(*args, **kwargs):
if stack:
return f(*args, **kwargs)
else:
to = f(*args, **kwargs)
while True:
if isinstance(to, GeneratorType):
stack.append(to)
to = next(to)
else:
stack.pop()
if not stack:
break
to = stack[-1].send(to)
return to
return wrappedfunc
letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65)
num_to_letter = staticmethod(lambda x: ascii_uppercase[x])
array = staticmethod(lambda x=0, size=N: [x] * size)
array2d = staticmethod(
lambda x=0, rows=N, cols=M: [std.array(x, cols) for _ in range(rows)])
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
filter = staticmethod(lambda func, iterable: list(filter(func, iterable)))
n, = read()
w = std.array(0, N)
f = [std.array2d(0, N, N) for _ in range(N * 2)]
while True:
x, y, num = read()
if x + y + num == 0:
break
w[x][y] = num
for k in range(2, n + n + 1):
for i1 in range(1, n + 1):
for i2 in range(1, n + 1):
j1 = k - i1
j2 = k - i2
if 1 <= j1 <= n and 1 <= j2 <= n:
t = w[i1][j1]
if i1 != i2:
t += w[i2][j2]
f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t,
f[k - 1][i1 - 1][i2] + t,
f[k - 1][i1][i2 - 1] + t,
f[k - 1][i1][i2] + t)
print(f[n + n][n][n])
|
