Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <array>
- #include <bitset>
- #include <cassert>
- #include <climits>
- #include <cmath>
- #include <complex>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <ctime>
- #include <deque>
- #include <functional>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <random>
- #include <set>
- #include <sstream>
- #include <string>
- #include <tgmath.h>
- #include <tuple>
- #include <unistd.h>
- #include <unordered_map>
- #include <unordered_set>
- #include <vector>
- using namespace std;
- typedef long long int lli;
- typedef pair<int, int> pii;
- typedef pair<lli, lli> plli;
- typedef unsigned char byte;
- typedef unsigned int uint;
- typedef unsigned long long int ulli;
- const int UP = 0;
- const int LEFT = 1;
- const int RIGHT = 2;
- int arr[1200][1200];
- int dp[1200][1200][3];
- inline int max3(int a, int b, int c)
- {
- return max(max(a, b), c);
- }
- inline int max4(int a, int b, int c, int d)
- {
- return max(max(a, b), max(c, d));
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("in.txt", "r", stdin);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m;
- scanf("%d %d", &n, &m);
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= m; j++)
- scanf("%d", &arr[i][j]);
- for(int i = 1; i <= n; i++)
- for(int j = 1; j <= m; j++)
- dp[i][j][UP] = dp[i][j][LEFT] = dp[i][j][RIGHT] = -2e9;
- dp[1][1][UP] = arr[1][1];
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- if(i > 1) dp[i][j][UP] = max4(dp[i][j][UP], dp[i-1][j][UP] + arr[i][j], dp[i-1][j][LEFT] + arr[i][j], dp[i-1][j][RIGHT] + arr[i][j]);
- if(j > 1) dp[i][j][LEFT] = max3(dp[i][j][LEFT], dp[i][j-1][UP] + arr[i][j], dp[i][j-1][LEFT] + arr[i][j]);
- if(j < m) dp[i][j][RIGHT] = max3(dp[i][j][RIGHT], dp[i][j+1][UP] + arr[i][j], dp[i][j+1][RIGHT] + arr[i][j]);
- }
- }
- for(int i = 1; i <= n; i++)
- {
- for(int j = m; j >= 1; j--)
- {
- if(i > 1) dp[i][j][UP] = max4(dp[i][j][UP], dp[i-1][j][UP] + arr[i][j], dp[i-1][j][LEFT] + arr[i][j], dp[i-1][j][RIGHT] + arr[i][j]);
- if(j > 1) dp[i][j][LEFT] = max3(dp[i][j][LEFT], dp[i][j-1][UP] + arr[i][j], dp[i][j-1][LEFT] + arr[i][j]);
- if(j < m) dp[i][j][RIGHT] = max3(dp[i][j][RIGHT], dp[i][j+1][UP] + arr[i][j], dp[i][j+1][RIGHT] + arr[i][j]);
- }
- }
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- if(dp[i][j][0] < -1e9) dp[i][j][0] = -99;
- if(dp[i][j][1] < -1e9) dp[i][j][1] = -99;
- if(dp[i][j][2] < -1e9) dp[i][j][2] = -99;
- printf("(%03d, %03d, %03d) ", dp[i][j][0], dp[i][j][1], dp[i][j][2]);
- }
- puts("");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement