█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5837

Problema 0x50 - Rectángulo de máxima área dentro de un histograma enorme

  • Autor: nivalderramas
  • Fecha: 2022-03-10 20:23:56 UTC (Hace alrededor de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.003 s 0 KBi
#2
Incorrecto
0.004 s 21 KBi
#3
Correcto
0.002 s 0 KBi
#4
Incorrecto
0.002 s 0 KBi
#5
Incorrecto
0.002 s 0 KBi
#6
Incorrecto
0.001 s 0 KBi
#7
Incorrecto
0.001 s 0 KBi
#8
Incorrecto
0.002 s 0 KBi
#9
Correcto
0.002 s 0 KBi
#10
Incorrecto
0.005 s 24 KBi
#11
Incorrecto
0.004 s 12 KBi
#12
Incorrecto
0.002 s 0 KBi
#13
Incorrecto
0.002 s 0 KBi
#14
Incorrecto
0.041 s 2 KBi
#15
Incorrecto
0.035 s 2 KBi
#16
Incorrecto
0.048 s 2 KBi
#17
Incorrecto
0.048 s 3 KBi
#18
Incorrecto
0.019 s 2 KBi
#19
Incorrecto
0.02 s 2 KBi
#20
Incorrecto
0.022 s 2 KBi
#21
Incorrecto
0.041 s 2 KBi
#22
Incorrecto
0.055 s 2 KBi
#23
Incorrecto
0.048 s 2 KBi
#24
Incorrecto
0.019 s 2 KBi
#25
Incorrecto
0.021 s 2 KBi
#26
Incorrecto
0.028 s 2 KBi
#27
Incorrecto
0.018 s 2 KBi
#28
Incorrecto
0.019 s 2 KBi
#29
Incorrecto
0.021 s 2 KBi
Puntos totales: 11 / 100

Código

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<n;i++)
#define pb push_back
#define ff first
#define ss second
#include <assert.h>
#define ii pair<int,int>
#define vi vector<lli>
#define vii vector<ii>
#define lli long long int
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
ostream& operator<<(ostream& os, const vector<lli> &v){
    for(auto const &i: v){
        os<<i<<" ";
    }
    os<<endl;
    return os;
}
const lli mod=(1e9)+7;
const int N = 1e4+1;
int main(){
    fast_io;
    int n;cin>>n;
    vi nums;
    lli tmp;
    for(int i = 0; i < n; i++){
        cin>>tmp;
        nums.pb(tmp);
    }
    stack<int> st;
    vi der(n,0);
    for(int i = n-1; i>=0; i--){
        lli dis = 0;
        while(st.size() > 0 && st.top() >= nums[i]){
            dis++;
            st.pop();
        }
        st.push(nums[i]);
        der[i] = dis;
    }
    lli ans = 0;
    for(int i = 0; i<n; i++){
        lli dis = 0;
        while(st.size() > 0 &&        nums[i]){
            dis++;
            st.pop();
        }
        st.push(nums[i]);
        der[i] = max(der[i],dis);
        ans = max(ans,(der[i]+1)*nums[i]);
    }
    cout<<ans<<endl;
    return 0;
}