Advertisement
Guest User

Untitled

a guest
Aug 21st, 2019
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.78 KB | None | 0 0
  1. #include <algorithm>
  2. #include <array>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <climits>
  6. #include <cmath>
  7. #include <complex>
  8. #include <cstdio>
  9. #include <cstdlib>
  10. #include <cstring>
  11. #include <ctime>
  12. #include <deque>
  13. #include <functional>
  14. #include <iostream>
  15. #include <map>
  16. #include <queue>
  17. #include <random>
  18. #include <set>
  19. #include <sstream>
  20. #include <string>
  21. #include <tgmath.h>
  22. #include <tuple>
  23. #include <unistd.h>
  24. #include <unordered_map>
  25. #include <unordered_set>
  26. #include <vector>
  27. using namespace std;
  28.  
  29. typedef long long int lli;
  30. typedef pair<int, int> pii;
  31. typedef pair<lli, lli> plli;
  32. typedef unsigned char byte;
  33. typedef unsigned int uint;
  34. typedef unsigned long long int ulli;
  35.  
  36. const int UP = 0;
  37. const int LEFT = 1;
  38. const int RIGHT = 2;
  39.  
  40. int arr[1200][1200];
  41. int dp[1200][1200][3];
  42.  
  43. inline int max3(int a, int b, int c)
  44. {
  45.     return max(max(a, b), c);
  46. }
  47.  
  48. inline int max4(int a, int b, int c, int d)
  49. {
  50.     return max(max(a, b), max(c, d));
  51. }
  52.  
  53. int main()
  54. {
  55. #ifndef ONLINE_JUDGE
  56.     freopen("in.txt", "r", stdin);
  57. #endif
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(nullptr);
  60.  
  61.     int n, m;
  62.     scanf("%d %d", &n, &m);
  63.  
  64.     for(int i = 1; i <= n; i++)
  65.         for(int j = 1; j <= m; j++)
  66.             scanf("%d", &arr[i][j]);
  67.  
  68.     for(int i = 1; i <= n; i++)
  69.         for(int j = 1; j <= m; j++)
  70.             dp[i][j][UP] = dp[i][j][LEFT] = dp[i][j][RIGHT] = -2e9;
  71.  
  72.     dp[1][1][UP] = arr[1][1];
  73.     for(int i = 1; i <= n; i++)
  74.     {
  75.         for(int j = 1; j <= m; j++)
  76.         {
  77.             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]);
  78.             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]);
  79.             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]);
  80.         }
  81.     }
  82.  
  83.     for(int i = 1; i <= n; i++)
  84.     {
  85.         for(int j = m; j >= 1; j--)
  86.         {
  87.             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]);
  88.             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]);
  89.             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]);
  90.         }
  91.     }
  92.  
  93.     for(int i = 1; i <= n; i++)
  94.     {
  95.         for(int j = 1; j <= m; j++)
  96.         {
  97.             if(dp[i][j][0] < -1e9) dp[i][j][0] = -99;
  98.             if(dp[i][j][1] < -1e9) dp[i][j][1] = -99;
  99.             if(dp[i][j][2] < -1e9) dp[i][j][2] = -99;
  100.             printf("(%03d, %03d, %03d) ", dp[i][j][0], dp[i][j][1], dp[i][j][2]);
  101.         }
  102.         puts("");
  103.     }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement