codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <cstdio> #include <cstdlib> #include <algorithm> #define MAX 1010 using namespace std; typedef long long ll; int N; int val[MAX][MAX]; ll dp[MAX][MAX]; int main(){ while(scanf("%d", &N) && N != 0){ for(int i = 0; i < MAX; i++) for(int j = 0; j < MAX; j++) dp[i][j] = 0; for(int i = 0; i < N; i++) for(int j = 0; j <= i; j++){ scanf("%d", &val[i-j+1][j+1]); } N++; for(int i = 1; i < N; i++){ for(int j = 1; j <= N-i; j++) dp[i][j] = val[i][j] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]; } ll resp = 0; for(int i = 1; i < N; i++){ for(int j = N-i; j > 0; j--){ ll col = dp[i][j] - dp[i][j-1]; //printf ("%lld\n", col); resp = max(resp, dp[i][j] + dp[i-1][j+1]); dp[i][j] = max( max(col, col+dp[i-1][j+1]), max(dp[i-1][j], dp[i][j+1] + col)); } } printf("%lld\n", resp); } return 0; }
Private
[
?
]
Run code
Submit