fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int n;
  6.     cin>>n;
  7.     int arr[n];
  8.     for(int i = 0; i < n; i++){
  9.         cin>>arr[i];
  10.     }
  11.  
  12.     stack<int> st;
  13.     int maxArea = 0;
  14.  
  15.     st.push(0);
  16.  
  17.     for(int i = 1; i < n; i++){
  18.         if( arr[i] >= arr[st.top()] || st.empty()){
  19.             st.push(i);
  20.         }else{
  21.             while(arr[st.top()] > arr[i]){
  22.                 int minHght = arr[st.top()];
  23.                 st.pop();
  24.                 if(st.size() != 0){
  25.                     int top = st.top();
  26.                     int currArea = (i - top - 1)*minHght;
  27.                     if(currArea > maxArea){
  28.                         maxArea = currArea;
  29.                     }
  30.                 }else{
  31.                     int currArea = i*minHght;
  32.                     if(currArea > maxArea){
  33.                         maxArea = currArea;
  34.                     }
  35.                     break;
  36.                 }
  37.             }
  38.             st.push(i);
  39.         }
  40.     }
  41.  
  42.     while(st.size() != 0){
  43.         int minHght = arr[st.top()];
  44.         st.pop();
  45.         if(st.size() != 0){
  46.             int top = st.top();
  47.             int currArea = (n - top - 1)*minHght;
  48.             if(currArea > maxArea){
  49.                 maxArea = currArea;
  50.             }
  51.         }else{
  52.             int currArea = n*minHght;
  53.             if(currArea > maxArea){
  54.                 maxArea = currArea;
  55.             }
  56.             break;
  57.         }
  58.     }
  59.     cout<<maxArea;
  60. 	return 0;
  61. }
Time limit exceeded #stdin #stdout 5s 4376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MRrXr3
Histogram
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!