Cod sursa(job #2051116)

Utilizator giotoPopescu Ioan gioto Data 28 octombrie 2017 15:56:56
Problema Progresie Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

int n, m;
int st[2005], e[2005];
int a[1005][1005], c[2005][2005];
bool f[2005][2005];
int main()
{
    freopen("jmenoasa.in", "r", stdin);
    freopen("jmenoasa.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; ++i)
        for(int j = 1; j <= m ; ++j)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n ; ++i){
        for(int j = 1; j <= m ; ++j){
//            f[i * 2 - 1][j * 2 - 1] = a[i][j];
            if(j < m) if(a[i][j] < a[i][j + 1]) f[i * 2 - 1][j * 2] = 0;
                      else f[i * 2 - 1][j * 2] = 1;
            if(i < n) if(a[i][j] < a[i + 1][j]) f[i * 2][j * 2 - 1] = 0;
                      else f[i * 2][j * 2 - 1] = 1;
        }
    }
    n = n * 2 - 1; m = m * 2 - 1;
    long long Sol = 0;
    for(int i = 1; i <= n ; i += 2){
        int top = 0;
        for(int j = 1; j <= m + 1; j += 2){
            int h = c[i][j], l = 1;
            int L = e[top];
            if(j == m + 1) l = 0;
            if(j % 2 == 0) while(h < st[top]) --top;
            else{
                while(h < st[top]){
                    Sol = max(Sol, 1LL * h * (L - e[top - 1]));
                    --top;
                }
            }
            st[++top] = j;
            e[top] = L + l;
        }
    }
    printf("%lld", Sol);
    return 0;
}