Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- using namespace std;
- const int N = 105;
- int m, n, g[N][N], dp[N*2][N][N];
- inline bool good(int i, int j){
- return j >= 0 and i - j >= 0 and j < m and i - j < n and g[j][i - j] != -1;
- }
- int main(){
- ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- cin >> m >> n;
- for(int i = 0; i < m; ++i){
- for(int j = 0; j < n; ++j){
- cin >> g[i][j];
- }
- }
- // from (0, 0) to (m-1, n-1)
- for(int i = 0; i <= m + n - 2; ++i){
- for(int j = 0; j <= i; ++j){
- if(!good(i, j)) continue;
- for(int k = 0; k <= i; ++k){
- if(!good(i, k)) continue;
- dp[i][j][k] = g[j][i - j] + (j != k ? g[k][i - k] : 0);
- int mx = 0;
- if(good(i-1, j) and good(i-1, k))
- mx = max(mx, dp[i-1][j][k]);
- if(good(i-1, j) and good(i-1, k-1))
- mx = max(mx, dp[i-1][j][k-1]);
- if(good(i-1, j-1) and good(i-1, k))
- mx = max(mx, dp[i-1][j-1][k]);
- if(good(i-1, j-1) and good(i-1, k-1))
- mx = max(mx, dp[i-1][j-1][k-1]);
- dp[i][j][k] += mx;
- }
- }
- }
- cout << dp[m + n - 2][m-1][m-1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement