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
| #include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, a[505][155], f1[155][155], f2[155][155], f3[155][155], f4, f5[155][155], f6[155][155], f7[155][155], f8;
int f9[155][155], f10[155][155], f11[155][155], s1[155], s2[155][155], s3[155][155], oo, ans;
void c(int b[155][155]){
memset(b, -63, sizeof(int)*155*155);
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++){
int uu;
scanf("%d", &uu);
a[j][n-i+1] = uu;
}
c(f1); c(f2); c(f3); c(f5); c(f6); c(f7); c(f9); c(f10); c(f11); c(s2); c(s3);
ans = oo = f4 = f8 = f1[1][1];
for(int j=1; j<=m; j++){
for(int i=1; i<=n; i++) s1[i] = s1[i-1] + a[j][i];
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++){
f11[l][r] = max(f11[l][r], f10[l][r]) + a[j][l] + a[j][r];
ans = max(ans, f11[l][r]);
}
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++)
f10[l][r] = max(f9[l][r], f10[l][r]) + s1[r] - s1[l-1];
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++)
f9[l][r] = max(f8, f9[l][r]) + a[j][l] + a[j][r];
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++)
f8 = max(f8, f7[l][r]);
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++)
f7[l][r] = f6[l][r] + s1[r] - s1[l-1];
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++)
f6[l][r] = max(f5[l][r], f6[l][r]) + a[j][l] + a[j][r];
for(int l=1; l<=n; l++)
for(int r=l+2; r<=n; r++)
f5[l][r] = f4 + s1[r] - s1[l-1];
for(int l=1; l<=n; l++)
for(int r=l+1; r<=n; r++)
f4 = max(f4, f3[l][r]);
for(int l=1; l<=n; l++){
int tmp=oo;
for(int r=l+1; r<=n; r++){
tmp = max(tmp, f2[l][r-1]);
f3[l][r] = max(f3[l][r], tmp) + s1[r] - s1[l-1];
}
}
for(int r=1; r<=n; r++){
int tmp=s2[r+1][r+1];
for(int l=r; l; l--){
tmp = max(tmp, s2[l][r]);
f2[l][r] = max(s3[l-1][r], tmp) + s1[r] - s1[l-1];
}
}
for(int l=1; l<=n; l++)
for(int r=l+1; r<=n; r++)
f1[l][r] = max(0, f1[l][r]) + s1[r] - s1[l-1];
for(int l=n; l; l--)
for(int r=n; r>=l; r--)
s2[l][r] = max(f2[l][r], s2[l][r+1]);
for(int r=1; r<=n; r++)
for(int l=1; l<=r; l++)
s3[l][r] = max(f1[l][r], s3[l-1][r]);
}
cout<<ans<<endl;
return 0;
}
|
