Submission #618107

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

template<class Value, bool rangeAdd = false> class CumulativeSum2D {
private:
  struct RangeValue {
    int i, j, y, x;
    Value v;
    RangeValue(int i, int j, int y, int x, Value v) : i(i), j(j), y(y), x(x), v(v) {}
  };

  vector<vector<Value>> val;
  vector<RangeValue> rangeValue;

public:
  CumulativeSum2D() {}

  CumulativeSum2D(int n, int m) : val(n + 1, vector<Value>(m + 1, Value(0))) {}
  
  template<typename T> CumulativeSum2D(T v) {
    int n = v.size();
    int m = v.front().size();
    for (int i = 0; i < n + 1; ++i) val.emplace_back(m + 1, Value(0));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        val[i + 1][j + 1] = val[i][j + 1] + val[i + 1][j] - val[i][j] + v[i][j];
      }
    }
  }

  void add(int i, int j, Value v) {
    add(i, j, i + 1, j + 1, v);
  }

  void add(int i, int j, int y, int x, Value v) {
    rangeValue.emplace_back(i, j, y, x, v);
  }

  // [(i,j), (y,x))
  Value sum(int i, int j, int y, int x) {
    if (rangeAdd && !rangeValue.empty()) {
      int n = val.size() - 1;
      int m = val.front().size() - 1;
      for (int k = 0; k < 2; ++k) {
        for (int i = 0; i < n; ++i) {
          for (int j = 0; j < m; ++j) {
            val[i + 1][j + 1] = val[i + 1][j + 1] - val[i][j + 1] - val[i + 1][j] + val[i][j];
          }
        }
      }
      for (const auto& v : rangeValue) {
        val[v.i + 1][v.j + 1] += v.v;
        if (v.y < n) val[v.y + 1][v.j + 1] -= v.v;
        if (v.x < m) val[v.i + 1][v.x + 1] -= v.v;
        if (v.y < n && v.x < m) val[v.y + 1][v.x + 1] += v.v;
      }
      for (int k = 0; k < 2; ++k) {
        for (int i = 0; i < n; ++i) {
          for (int j = 0; j < m; ++j) {
            val[i + 1][j + 1] += val[i][j + 1] + val[i + 1][j] - val[i][j];
          }
        }
      }
      rangeValue.clear();
    }
    return val[y][x] - val[i][x] - val[y][j] + val[i][j];
  }

  Value value(int i, int j) {
    return sum(i, j, i + 1, j + 1);
  }
};

template <typename T> inline istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template <typename T> inline ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

template<typename T> T min(vector<T>& v) {return *min_element(v.begin(), v.end());}

template<typename T> T max(vector<T>& v) {return *max_element(v.begin(), v.end());}

template<typename T> void sort(vector<T>& v) {sort(v.begin(), v.end());}

template<typename T, typename Function> void sort(vector<T>& v, Function func) {sort(v.begin(), v.end(), func);}

template<typename T> void rsort(vector<T>& v) {sort(v.rbegin(), v.rend());}

template<typename T> void reverse(vector<T>& v) {reverse(v.begin(), v.end());}

template<typename T> void unique(vector<T>& v) {v.erase(unique(v.begin(), v.end()), v.end());}

template<typename T> void nth_element(vector<T>& v, int n) {nth_element(v.begin(), v.begin() + n, v.end());}

template<typename T> bool next_permutation(vector<T>& v) {return next_permutation(v.begin(), v.end());}

template<typename T> int lower_bound(vector<T>& v, T t) {return lower_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> int upper_bound(vector<T>& v, T t) {return upper_bound(v.begin(), v.end(), t) - v.begin();}

template<typename T> T accumulate(vector<T>& v) {return accumulate(v.begin(), v.end(), T(0));}

template<typename T> void partial_sum(vector<T>& v, vector<T>& u) {partial_sum(v.begin(), v.end(), u.begin());}

template<typename T> T inner_product(vector<T>& v, vector<T>& u) {return inner_product(v.begin(), v.end(), u.begin(), T(0));}

template<typename T, typename Function> void remove_if(vector<T>& v, Function func) {v.erase(remove_if(v.begin(), v.end(), func), v.end());}

long long solve(const vector<vector<long long>>& b) {
  int h = b.size(), w = b[0].size();
  CumulativeSum2D<long long> sum(b);
  long long res = -1e18;
  vector<long long> dp1(w + 1, -1e18), dp2(w + 1, -1e18);
  for (int i = 0; i < h; ++i) for (int j = i + 1; j <= h; ++j) {
    vector<long long> d1(w + 1), d2(w + 1);
    for (int k = 0; k < w; ++k) {
      long long a = sum.sum(i, k, j, k + 1);
      dp1[k] = max(dp1[k], d1[k + 1] = max(d1[k] + a, a));
    }
    for (int k = w - 1; k >= 0; --k) {
      long long a = sum.sum(i, k, j, k + 1);
      dp2[k] = max(dp2[k], d2[k] = max(d2[k + 1] + a, a));
    }
  }
  for (int i = 0; i < w; ++i) for (int j = 0; j < i; ++j) for (int k = i; k < w; ++k) res = max(res, dp1[j] + dp2[k]);
  return res;
}

int main() {
  int h, w;
  cin >> h >> w;
  vector<vector<long long>> b(h, vector<long long>(w)), c(w, vector<long long>(h));
  cin >> b;
  for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) c[j][i] = b[i][j];
  cout << max(solve(b), solve(c)) << endl;
}

Submission Info

Judge Result