fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. ios::sync_with_stdio(0);
  6. cin.tie(0);
  7.  
  8. int n, m;
  9. cin >> n >> m;
  10. vector<vector<int>> a(n, vector<int>(m));
  11. for(int i = 0; i < n; i++)
  12. for(int j = 0; j < m; j++)
  13. cin >> a[i][j];
  14.  
  15. long long ans = LLONG_MIN;
  16.  
  17. // chọn hàng trên x
  18. for(int x = 0; x < n; x++){
  19. vector<int> colSum(m, 0); // V[i]
  20.  
  21. // chọn hàng dưới u
  22. for(int u = x + 1; u < n; u++){
  23. // cập nhật V[i] += a[u-1][i]
  24. for(int c = 0; c < m; c++)
  25. colSum[c] += (u - x > 1 ? a[u-1][c] : 0);
  26.  
  27. // tạo H[i]
  28. vector<long long> H(m);
  29. for(int c = 0; c < m; c++)
  30. H[c] = a[x][c] + a[u][c];
  31.  
  32. // prefix sum của H
  33. vector<long long> pref(m+1, 0);
  34. for(int c = 0; c < m; c++)
  35. pref[c+1] = pref[c] + H[c];
  36.  
  37. long long bestLeft = LLONG_MIN;
  38.  
  39. // quét cột v (phải)
  40. for(int v = 1; v < m; v++){
  41. // cập nhật best y
  42. long long yValue = colSum[v-1] + H[v-1] - pref[v-1];
  43. bestLeft = max(bestLeft, yValue);
  44.  
  45. long long curr = bestLeft + colSum[v] + H[v] + pref[v];
  46. ans = max(ans, curr);
  47. }
  48. }
  49. }
  50.  
  51. cout << ans;
  52. }
  53.  
Success #stdin #stdout 0s 5320KB
stdin
3 4
1 1 1 1
1 -5 -5 1
1 1 1 1
stdout
12