Cod sursa(job #2552161)

Utilizator NeganAlex Mihalcea Negan Data 20 februarie 2020 17:10:31
Problema DreptPal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("dreptpal.in");
ofstream fout("dreptpal.out");
int a[1010][1010];
int t[1010];
int st[1010];
int s[1010], d[1010];
int n, m, top;
int calcul()
{
    int i;
    t[n + 1] = -1;
    st[0] = 0;
    top = 0;
    for(i = 1;i <= n;i++)
    {
        while(t[st[top]] >= t[i])
            top--;
        s[i] = i - st[top];
        st[++top] = i;
    }
    top = 0;
    st[0] = n + 1;
    for(i = n;i >= 1;i--)
    {
        while(t[st[top]] >= t[i])
            top--;
        d[i] = st[top] - i;
        st[++top] = i;
    }
    int M = 0;
    for(i = 1;i <= n;i++)
        M = max(M, (s[i] + d[i] - 1) * t[i]);
    return M;
}
int main()
{
    int i, j, x, y, amax = 0;
    fin >> n >> m;
    t[0] = -1;
    t[m + 1] = -2;
    for(i = 1;i <= n;i++)
    {
        for(j = 1;j <= m;j++)
            fin >> t[j];
        for(j = 1;j <= m;j++)
        {
            x = y = j;
            while(t[x] == t[y])
            {
                x--;
                y++;
            }
            a[i][j] = y - x - 1;
        }
    }
    /*for(i = 1;i <= n;i++, cout << "\n")
        for(j = 1;j <= m;j++)
            cout << a[i][j] << " ";*/
    for(j = 1;j <= m;j++)
    {
        for(i = 1;i <= n;i++)
            t[i] = a[i][j];
        x = calcul();
        amax = max(amax, x);
    }
    fout << amax;
    return 0;
}