Submission #43887409

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#ifndef ONLINE_JUDGE
  #include "/home/muhesh/cp/debug.h"
#endif

#define int long long
#define vt vector
#define ar array
#define nl '\n'

typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ld, ld> pd;

typedef vt<int> vi;
typedef vt<ld> vd;
typedef vt<pi> vpi;
typedef vt<string> vs;
typedef vt<vi> vvi;

#define r_ep(i, a, b, s) for(int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define rep1(e) r_ep(i, 0, e, 1)
#define rep2(i, e) r_ep(i, 0, e, 1)
#define rep3(i, b, e) r_ep(i, b, e, 1)
#define rep4(i, b, e, s) r_ep(i, b, e, s)
#define get5(a, b, c, d, e, ...) e
#define repc(...) get5(__VA_ARGS__, rep4, rep3, rep2, rep1)
#define rep(...) repc(__VA_ARGS__)(__VA_ARGS__)
#define each(i, a) for (auto &i: a)

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define amin(a, b) a = min(a, b)
#define amax(a, b) a = max(a, b)
#define sz(x) (int) (x).size()
#define bg(x) (x).begin()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define mt make_tuple
#define fr first
#define sc second
#define ft front()
#define bk back()

inline namespace IO {
  string to_string(char c) { return string(1, c); }
  string to_string(bool b) { return b ? "true" : "false"; }
  string to_string(const char * s) { return string(s); }
  string to_string(string s) { return s; }
  template<class T>
  string to_string(T x) { return std::to_string(x); }
  template<class A, class B>
  string to_string(pair<A, B> &a) { 
    return to_string(a.fr) + " " + to_string(a.sc); 
  }

  template<class T> void read(T &x) { cin >> x; }
  void read(float &d) { string t; read(t); d = stof(t); }
  void read(double &d) { string t; read(t); d = stod(t); }
  void read(ld &d) { string t; read(t); d = stold(t); }
  template<class A, class B> void read(pair<A, B> &a) {
    read(a.fr); read(a.sc);
  }
  template<class A> void read(vt<A> &a) { each(i, a) read(i); }
  template<class H, class... T> void read(H &h, T&... t) {
    read(h); read(t...);
  }

  template<class T> void write(T x) { cout << to_string(x); }
  template<class H, class... T> void write(const H &h, const T&... t) {
    write(h); write(t...); 
  }

  void print() { write("\n"); }
  template<class T> void print(vt<T> x) { 
    each(i, x) { write(i); write(" "); }
    print();
  }
  template<class H, class... T> void print(const H &h, const T&... t) {
    write(h); if (sizeof...(t)) write(' '); print(t...);
  }
}

inline namespace FileIO {
  void setIn(string s) { freopen(s.c_str(), "r", stdin); }
  void setOut(string s) { freopen(s.c_str(), "w", stdout); }
  void setIO(string s = "") {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (!s.empty()) setIn(s + ".in"), setOut(s + ".out");
  }
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
const int MOD = MOD1;
// const int INF = 2e18;
const double PI = acos(-1.0);

struct chash { // use most bits rather than just the lowest ones
  const uint64_t C = (long long) (2e18 * PI) + 71; // large odd number
  const int RANDOM = rng(); // random 32-bit number
  long long operator() (long long x) const {
    // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
    return __builtin_bswap64((x ^ RANDOM) * C);
  }
};

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
tree_order_statistics_node_update>;

template<class T>
using ordered_multiset = tree<pair<T, T>, null_type, less<pair<T, T>>, 
rb_tree_tag, tree_order_statistics_node_update>;

template<class K, class V> using ht = gp_hash_table<K, V, chash>;
template<class K> using hash_set = ht<K, null_type>;
template<class K, class V> using hash_table = ht<K, V>;

class PrefixSumMatrix {
 private:
  int n, m;
  vector<vector<int>> pa;
  bool is_zero_based;
  bool is_lower_left_top_right;
  
 public:
  void build(const vector<vector<int>> &a) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        pa[i][j] = (
          (is_zero_based ? a[i - 1][j - 1] : a[i][j]) +
          pa[i - 1][j] + 
          pa[i][j - 1] - 
          pa[i - 1][j - 1]
        );
      }
    }
  } 
  
  int get(int a, int b, int c, int d) {
    if (is_zero_based) a++; b++; c++; d++;
    if (is_lower_left_top_right) swap(b, d);
    return (
      pa[c][d] - 
      pa[a - 1][d] - 
      pa[c][b - 1] +
      pa[a - 1][b - 1]
    );
  }

  PrefixSumMatrix() { }

  PrefixSumMatrix(
    const vector<vector<int>> a, 
    bool is_zero_based = true,
    bool is_lower_left_top_right = false
  ) {
    int n = a.size(), m = a[0].size();
    this -> is_zero_based = is_zero_based;
    this -> is_lower_left_top_right = is_lower_left_top_right;
    this -> n = n;
    this -> m = m;
    pa.assign(n + 1, vector<int>(m + 1, 0));
    build(a);
  }
};

vector<int> get_prev_smaller_element_idx(const vector<int> &a) {
  int n = size(a);
  vector<int> prev_smaller_element_idx(n);
  stack<int> st;
  for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.top()] >= a[i])
      st.pop();
    prev_smaller_element_idx[i] = (st.empty() ? -1 : st.top());
    st.push(i);
  }
  return prev_smaller_element_idx;
}

vector<int> get_next_smaller_element_idx(const vector<int> &a) {
  int n = size(a);
  vector<int> next_smaller_element_idx(n);
  stack<int> st;
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && a[st.top()] >= a[i])
      st.pop();
    next_smaller_element_idx[i] = (st.empty() ? n : st.top());
    st.push(i);
  }
  return next_smaller_element_idx;
}

int get_maximum_sum_histogram(const vector<int>& a, PrefixSumMatrix& psm, int row) {
  auto prev_smaller_element_idx = get_prev_smaller_element_idx(a);
  auto next_smaller_element_idx = get_next_smaller_element_idx(a);

  int n = size(a);
  int maximum_area = 0, mx_sum = 0;
  for (int i = 0; i < n; i++) {
    int width = next_smaller_element_idx[i] - prev_smaller_element_idx[i] - 1;
    int height = a[i];
    int area = height * width;
    int sum = psm.get(row - height + 1, prev_smaller_element_idx[i] + 1, row, next_smaller_element_idx[i] - 1);
    maximum_area = max(area, maximum_area);
    mx_sum = max(mx_sum, sum);
  }
  return mx_sum;
}

int get_mx_area_from_rectangle(const vector<vector<int>>& matrix, int target, PrefixSumMatrix& psm) {
  int n = size(matrix);
  if (n == 0) return 0;
  
  int m = size(matrix.front());
  vector<int> histograms(m);
  for (int j = 0; j < m; j++) {
    histograms[j] = matrix[0][j] >= target;
  }
  
  int mx_area = get_maximum_sum_histogram(histograms, psm, 0);
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < m; j++) {
      histograms[j] = matrix[i][j] >= target ? histograms[j] + 1 : 0;
    }
    mx_area = max(mx_area, get_maximum_sum_histogram(histograms, psm, i));
  }
  return mx_area;
}

void solve() {
  int n, m; read(n, m);
  vvi a(n, vi(m)); read(a);
  PrefixSumMatrix psm(a);
  int ans = 0;
  rep(val, 1, 301) { // O(300 * n * m)
    int sum_rectangluar_area = get_mx_area_from_rectangle(a, val, psm);
    amax(ans, sum_rectangluar_area * val);
  }
  print(ans);
}

int32_t main() {
  setIO();

  int tc = 1;
  // read(tc);
  rep(i, 1, tc + 1) {
    // write("Case #", i, ": ");
    solve();
  }

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In member function ‘long long int PrefixSumMatrix::get(long long int, long long int, long long int, long long int)’:
./Main.cpp:154:5: warning: this ‘if’ clause does not guard... [-Wmisleading-indentation]
  154 |     if (is_zero_based) a++; b++; c++; d++;
      |     ^~
./Main.cpp:154:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘if’
  154 |     if (is_zero_based) a++; b++; c++; d++;
      |                             ^
./Main.cpp: In function ‘void FileIO::setIn(std::string)’:
./Main.cpp:94:33: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
   94 |   void setIn(string s) { freopen(s.c_str(), "r", stdin); }
      |                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp: In function ‘void FileIO::setOut(std::string)’:
./Main.cpp:95:34: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
   95 |   void setOut(string s) { freopen(s.c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Judge Result