pbinfo/Matrix2.cpp at main · patrick-burasan24/pbinfo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <fstream>

using namespace std;

ifstream cin("matrix2.in");
ofstream cout("matrix2.out");

const int NMAX = 1005;
int n, m, top, maxi, stg[NMAX], drp[NMAX], st[NMAX], mat[NMAX][NMAX], s[NMAX][NMAX];

void Citire() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> mat[i][j];
}

void Rezolvare() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (mat[i][j] == 1)
                s[i][j] = 0;
            else
                s[i][j] = 1 + s[i - 1][j];
    maxi = -1;
    for (int i = 1; i <= n; i++) {
        s[i][0] = s[i][m + 1] = -1;
        top = 0;
        st[++top] = 0;
        for (int j = 1; j <= m; j++) {
            while (s[i][st[top]] >= s[i][j])
                top--;
            stg[j] = j - st[top];
            st[++top] = j;
        }
        top = 0;
        st[++top] = m + 1;
        for (int j = m; j >= 1; j--) {
            while (s[i][st[top]] >= s[i][j])
                top--;
            drp[j] = st[top] - j;
            st[++top] = j;
        }
        for (int j = 1; j <= m; j++)
            maxi = max(maxi, s[i][j] * (stg[j] + drp[j] - 1));
    }
}

void Afisare() {
    cout << maxi << '\n';
}

int main() {
    Citire();
    Rezolvare();
    Afisare();
    cin.close();
    cout.close();
    return 0;
}