Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define len(v) (int)v.size()
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define pii pair<int, int>
- #define vi vector<int>
- #define vii vector<vector<int>>
- #define vpii vector<pair<int, int>>
- #define ull unsigned long long
- //#define int long long
- //#define ll ull
- const int N = 1e6 + 1;
- const int maxn = 5e6 + 10;
- const int C = 20;
- const int logn = 20;
- const ll inf = 1e9;
- const ll mod = 1e9 + 7;
- const int M = 1e9;
- const ull M2 = 998244353;
- const ld eps = 1e-6;
- using namespace std;
- template<class T>
- istream &operator>>(istream &in, vector<T> &a) {
- for (auto &i : a)
- in >> i;
- return in;
- }
- template<class T>
- ostream &operator<<(ostream &out, vector<T> &a) {
- for (auto &i : a)
- out << i << ' ';
- return out;
- }
- ll gist(vector<int>& b) {
- int n = len(b);
- vector<pii> s;
- s.emplace_back(0, -1);
- ll res = 0;
- for (int i = 0; i <= n; ++i) {
- int h;
- if (i < n) h = b[i];
- else h = 0;
- int x = i;
- while (h <= s.back().second) {
- x = s.back().first;
- int hprev = s.back().second;
- s.pop_back();
- ll area = 1ll * hprev * (i - x);
- if (area > res) res = area;
- }
- s.emplace_back(x, h);
- }
- return res;
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- vector<vector<int>> a(n, vector<int>(m));
- for (auto &i: a) {
- for (auto& el : i) {
- int x; cin >> x;
- el = (x ? 0 : 1);
- }
- }
- if (n == 1 && m == 1 && a[0][0] == 1) {
- cout << "1";
- return;
- }
- vector<vector<int>> p(n, vector<int>(m));
- p = a;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- if (p[i][j] && i > 0)
- p[i][j] += p[i - 1][j];
- }
- }
- ll ans = 0;
- for (int i = 0; i < n; ++i) {
- ans = max(ans, gist(p[i]));
- }
- cout << ans;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int T = 1;
- //cin >> T;
- while (T--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment