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
| #include <iostream>
#include <cstdio>
#define scan(x) scanf("%lld",&x)
#define f(i,a,b) for(int i=a;i<=b;i++)
#define pn(x,y) printf("###%lld:::%lld\n",x,y)
using namespace std;
typedef long long LL;
const LL N=1e3+1;
LL a[N][N],r,f[N][N];
struct FastIO {
static const int S = 5 << 20;
int wpos; char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar() {
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len) return -1;
return buf[pos ++];
}
inline int xuint() {
int c = xchar(), x = 0;
while(~c && c <= 32) c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline LL xull() {
int c = xchar();
LL x = 0;
while(~c && c <= 32) c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline int xint() {
int s = 1, c = xchar(), x = 0;
while(c <= 32) c = xchar();
if(c == '-') s = -1, c = xchar();
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x * s;
}
inline void xstring(char* s) {
int c = xchar();
while(c <= 32) c = xchar();
for(; c > 32; c = xchar()) * s++ = c;
*s = 0;
}
inline void wchar(int x) {
if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wll(LL x) {
if(x < 0) wchar('-'), x = -x;
char s[30];
int n = 0;
while(x || !n) s[n ++] = '0' + x % 10, x /= 10;
while(n--) wchar(s[n]);
}
inline void wstring(const char* s) {
while(*s) wchar(*s++);
}
~FastIO() {
if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;
LL dyp(LL i,LL j) {
if(i==r)return a[i-1][j];
if(f[i][j]!=-1)return f[i][j];
LL q=a[i-1][j]+(dyp(i+1,j)<dyp(i+1,j+1)?dyp(i+1,j+1):dyp(i+1,j));
f[i][j]=q;
return q;
}
int main() {
r=io.xint();
f(i,1,r) {
f(j,1,i) {
a[i-1][j-1]=io.xint();
f[i][j-1]=-1;
}
}
io.wll(dyp(1,0));
return 0;
}
|