Advertisement
BaoJIaoPisu

Untitled

Oct 11th, 2021
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("avx,avx2,fma")
  18. using namespace std;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. typedef long long ll;
  23. typedef pair<ll, ll> pll;
  24. typedef pair<int, int> pii;
  25.  
  26.  
  27. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  28. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  29. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  30.  
  31. const ll oo = 1e18;
  32. const ll maxN = 1e6;
  33.  
  34. /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
  35.  
  36. void maximize(int &a, int b) {
  37.     a = max(a, b);
  38. }
  39.  
  40. void minimize(int &a, int b) {
  41.     a = min(a, b);
  42. }
  43.  
  44. const int N = 5005;
  45. struct E {
  46.     int x, y, dist;
  47. };
  48. vector<E> ed;
  49. ll dp[N][3][2], ndp[N][3][2];
  50. int a[N];
  51.  
  52. void solve() {
  53.     int n, m;
  54.     cin >> n >> m;
  55.  
  56.     auto f = [&](int i, int j) -> int {
  57.         return (i - 1) * m + j;
  58.     };
  59.  
  60.     auto maximize = [&](ll &x, ll y) -> void {
  61.         if(x < y) x = y;
  62.     };
  63.  
  64.     auto minimize = [&](ll &x, ll y) -> void {
  65.         if(x > y) x = y;
  66.     };
  67.  
  68.     for(int i = 1; i <= n; i++) {
  69.         for(int j = 1; j <= m; j++) cin >> a[f(i, j)];
  70.     }
  71.  
  72.     for(int i = 1; i <= n; i++) {
  73.         for(int j = 1; j <= m; j++) {
  74.             int r = f(i, j);
  75.             dp[r][0][0] = dp[r][0][1] = a[r];
  76.             dp[r][1][0] = dp[r][2][0] = -oo;
  77.             dp[r][1][1] = dp[r][2][1] = oo;
  78.             for(int x = 0; x < 3; x++) {
  79.                 for(int y = 0; y < 2; y++) ndp[r][x][y] = dp[r][x][y];
  80.             }  
  81.  
  82.             if(i == 1 && j == 1) continue;
  83.             int dist = (i - 1) * (i - 1) + (j - 1) * (j - 1);
  84.             ed.pb({i - 1, j - 1, dist});
  85.         }
  86.     }
  87.  
  88.     sort(ed.begin(), ed.end(), [&](E _a, E _b) {
  89.         return _a.dist < _b.dist;
  90.     });
  91.  
  92.     int ed_num = ed.size(); ll ans = 0;
  93.     for(int c = 0; c < ed_num; c++) {
  94.         int x = ed[c].x, y = ed[c].y;
  95.         for(int i = 1; i <= n; i++) {
  96.             for(int j = 1; j <= m; j++) {
  97.                 int r = f(i, j);
  98.                 for(int ii = 0; ii < 2; ii++) {
  99.                     for(int jj = 0; jj < 2; jj++) {
  100.                         int fx = i + (ii ? x : -x);
  101.                         int fy = j + (jj ? y : -y);
  102.                         if(fx > 0 && fy > 0 && fx <= n && fy <= m) {
  103.                             int b = f(fx, fy);
  104.                             maximize(ndp[b][1][0], dp[r][0][0] + a[b]);
  105.                             maximize(ndp[b][2][0], dp[r][1][0] + a[b]);
  106.                             maximize(ndp[b][2][0], dp[r][2][0] + a[b]);
  107.                             minimize(ndp[b][1][1], dp[r][0][1] + a[b]);
  108.                             minimize(ndp[b][2][1], dp[r][1][1] + a[b]);
  109.                             minimize(ndp[b][2][1], dp[r][2][1] + a[b]);
  110.                         }
  111.                     }
  112.                 }
  113.             }
  114.         }
  115.  
  116.         if(c < ed_num - 1 && ed[c].dist < ed[c + 1].dist) {
  117.             for(int i = 1; i <= n * m; i++) {
  118.                 for(int x = 0; x < 3; x++) {
  119.                     for(int y = 0; y < 2; y++) {
  120.                         dp[i][x][y] = ndp[i][x][y];
  121.                     }
  122.                 }
  123.             }
  124.         }
  125.     }
  126.  
  127.     for(int i = 1; i <= n * m; i++) {
  128.         maximize(ans, ndp[i][2][0]);
  129.         maximize(ans, -ndp[i][2][1]);
  130.     }
  131.     cout << ans;
  132. }
  133.  
  134. int main()
  135. {
  136.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  137.     #ifndef ONLINE_JUDGE
  138.     freopen("input.txt", "r", stdin);
  139.     freopen("output.txt", "w", stdout);
  140.     #else
  141.     //online
  142.     #endif
  143.  
  144.     int tc = 1, ddd = 0;
  145.     // cin >> tc;
  146.     while(tc--) {
  147.         //ddd++;
  148.         //cout << "Case #" << ddd << ": ";
  149.         solve();
  150.     }
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement