Фермер

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll maxArea(vector<int> &h) {
    int n = h.size();
    stack<int> st;
    int L[n], R[n];

    for (int i = 0; i < n; ++i) {
        while (!st.empty() && h[st.top()] >= h[i]) {
            st.pop();
        }

        if (st.empty()) {
            L[i] = 0;
        } else {
            L[i] = st.top() + 1;
        }

        st.push(i);
    }

    while (!st.empty()) {
        st.pop();
    }

    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && h[st.top()] >= h[i]) {
            st.pop();
        }

        if (st.empty()) {
            R[i] = n - 1;
        } else {
            R[i] = st.top() - 1;
        }

        st.push(i);
    }

    ll ans = 0;

    for (int i = 0; i < n; ++i) {
        ans = max(ans, h[i] * (R[i] - L[i] + 1ll));
    }

    return ans;
}


int main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;
    int a[n][m];
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j) {
            a[i][j] = (s[j] - '0');
        }
    }

    vector<vector<int>> dp(n, vector<int> (m, 0));

    for (int j = 0; j < m; ++j) {
        dp[0][j] = a[0][j];
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            dp[i][j] = (dp[i - 1][j] * a[i][j] + a[i][j]);
        }
    }

    ll ans = 0;

    for (int i = 0; i < n; ++i) {
        ans = max(ans, maxArea(dp[i]));
    }

    cout << ans;

    return 0;
}

/*
dp[i][j] = сколько единиц подряд вверх начиная с i,j позиции

a
1 0 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 0 1 1 1

dp[i][j] = (dp[i-1][j] * a[i][j] + a[i][j]);
1 0 1 1 0 1 1 1 1 1
0 1 2 2 1 2 2 2 2 0
1 2 3 3 2 3 3 3 3 1
2 0 4 4 3 4 4 4 4 2
3 1 0 5 4 5 0 5 5 3
*/