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

Envío 5845

Problema 0x9c - Máximo elemento en un subarreglo enorme

  • Autor: nivalderramas
  • Fecha: 2022-03-10 22:19:33 UTC (Hace alrededor de 2 años)
Caso # Resultado Tiempo Memoria
#1
Incorrecto
0.003 s 0 KBi
#2
Incorrecto
0.003 s 0 KBi
#3
Incorrecto
0.001 s 0 KBi
#4
Incorrecto
0.001 s 0 KBi
#5
Incorrecto
0.005 s 2 KBi
#6
Incorrecto
0.001 s 0 KBi
#7
Incorrecto
0.002 s 0 KBi
#8
Incorrecto
0.004 s 2 KBi
#9
Incorrecto
0.004 s 2 KBi
#10
Incorrecto
0.004 s 0 KBi
#11
Incorrecto
0.03 s 3 KBi
#12
Incorrecto
0.058 s 3 KBi
#13
Incorrecto
0.032 s 3 KBi
#14
Incorrecto
0.03 s 3 KBi
#15
Incorrecto
0.057 s 3 KBi
Puntos totales: 0 / 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 vii vector<ii>
#define lli long long int
#define vi vector<lli>
#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;
    lli n;cin>>n;
    vi nums;
    lli tmp;
    for(int i = 0; i < n; i++){
        cin>>tmp;
        nums.pb(tmp);
    }
    stack<lli> st;
    vi der(n,n-1);
    st.push(n-1);
    for(int i = n-2; i>=0; i--){
        while(st.size() > 0 && nums[st.top()] >= nums[i]){
            st.pop();
        }
        der[i] = (st.size() ? st.top() -1 : n-1);
        st.push(i);
        
    }
    //cout<<der<<endl;
    while(st.size())st.pop();
    st.push(0);
    lli ans = 0;
    vi lef(n,-1);
    for(int i = 1; i<n; i++){
        while(st.size() > 0 && nums[st.top()] >= nums[i]){
            st.pop();
        }
        lef[i] = (st.size() ? st.top() +1 : 0);
        st.push(i);
        
    }
    //cout<<lef<<endl;
    for(int i = 0; i < n; i++){
        lli d = abs(i-der[i]+1);
        lli iz = abs(i-lef[i]+1);
        ans = max(ans,nums[i]*max(d,iz));
    }
    cout<<ans<<endl;
    return 0;
}