Advertisement
YEZAELP

o62_oct_c1_twoareas

Jan 26th, 2022 (edited)
772
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int inf = 1e9;
  5. const int N = 3e2;
  6. int ar[N + 10][N + 10], qs[N + 10][N + 10], two[N + 10][N + 10][N + 10], keep[N + 10][N + 10];
  7. int n, m, ans = 0;
  8.  
  9. void Reset(){
  10.     for(int i = 0; i <= N + 1; i ++){
  11.         for(int j = 0; j <= N + 1; j ++){
  12.             qs[i][j] = 0;
  13.             keep[i][j] = 0;
  14.             for(int k = 0; k <= N + 1; k ++)
  15.                 two[i][j][k] = -inf;
  16.         }
  17.     }
  18. }
  19.  
  20. void Solve(){
  21.  
  22.     Reset();
  23.  
  24.     /// Quick Sum
  25.     for(int i = 1; i <= n; i ++){
  26.         for(int j = 1; j <= m; j ++){
  27.             qs[i][j] = ar[i][j] + qs[i][j - 1];
  28.         }
  29.     }
  30.  
  31.     for(int l = 1; l <= m; l ++){
  32.         for(int r = l; r <= m; r ++){
  33.             int mx = 0;
  34.             for(int i = n; i >= 3; i --){
  35.                 int cur = qs[i][r] - qs[i][l - 1];
  36.                 mx = max(mx + cur, cur);
  37.                 two[i - 2][l][r] = mx;
  38.             }
  39.         }
  40.     }
  41.  
  42.     for(int i = n; i >= 1; i --){
  43.         for(int len = 1; len <= m; len ++){ /// ระวังตรงนี้
  44.                                             /// ให้ทำทีละความยาว เพราะ ถ้าทำโดย fix l ไว้แล้วค่อย ๆ เพิ่ม r จะทำให้ค่า               
  45.                                             /// max บางค่าไม่ได้มาจากรูปที่ใหญ่กว่า แต่อาจมาจากรูปที่เล็กกว่าก็ได้
  46.             for(int l = 1; l <= m - len + 1; l ++){
  47.                 int r = l + len - 1;
  48.                 for(int ll: {0, -1}){
  49.                     for(int rr: {0, 1}){
  50.                         for(int ii: {0, -1}){
  51.                             two[i + ii][l + ll][r + rr] = max(two[i + ii][l + ll][r + rr], two[i][l][r]);
  52.                         }
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }
  58.  
  59.     for(int l = 1; l <= m; l ++){
  60.         for(int r = l; r <= m; r ++){
  61.             int mx = 0;
  62.             for(int i = 1; i <= n; i ++){
  63.                 int cur = qs[i][r] - qs[i][l - 1];
  64.                 mx = max(mx + cur, cur);
  65.                 ans = max(ans, mx + two[i][l][r]);
  66.             }
  67.         }
  68.     }
  69. }
  70.  
  71. void Rotate(int ii = 1, int jj = m){
  72.     for(int i = 1; i <= n; i ++){
  73.         for(int j = 1; j <= m; j ++){
  74.             keep[i][j] = ar[i][j];
  75.         }
  76.     }
  77.  
  78.     for(int i = 1; i <= m; i ++){
  79.         ii = 1;
  80.         for(int j = 1; j <= n; j ++){
  81.             ar[i][j] = keep[ii][jj];
  82.             ii ++;
  83.         }
  84.         jj --;
  85.     }
  86.     swap(n, m);
  87. }
  88.  
  89. int main(){
  90.  
  91.     scanf("%d %d", &n, &m);
  92.  
  93.     for(int i = 1; i <= n; i ++){
  94.         for(int j = 1; j <= m; j ++){
  95.             scanf("%d", &ar[i][j]);
  96.         }
  97.     }
  98.  
  99.     Solve();
  100.  
  101.     Rotate();
  102.     Solve();
  103.  
  104.     Rotate();
  105.     Solve();
  106.  
  107.     Rotate();
  108.     Solve();
  109.  
  110.     printf("%d", ans);
  111.  
  112.     return 0;
  113. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement