SHARE
TWEET

code

theo830 Apr 24th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<stack>
  3. using namespace std;
  4. int getMaxArea(long long hist[], long long n){
  5.     stack<int> s;
  6.     int max_area = 0;
  7.     int tp;  
  8.     int area_with_top;
  9.     int i = 0;
  10.     while (i < n){
  11.         if (s.empty() || hist[s.top()] <= hist[i])
  12.             s.push(i++);
  13.         else{
  14.             tp = s.top();  
  15.             s.pop();
  16.             area_with_top = hist[tp] * (s.empty() ? i :
  17.                                    i - s.top() - 1);
  18.         if (max_area < area_with_top)
  19.                 max_area = area_with_top;
  20.         }
  21.     }
  22.     while (s.empty() == false){
  23.         tp = s.top();
  24.         s.pop();
  25.         area_with_top = hist[tp] * (s.empty() ? i :
  26.                                 i - s.top() - 1);
  27.         if (max_area < area_with_top)
  28.             max_area = area_with_top;
  29.     }
  30.     return max_area;
  31. }
  32. int main() {
  33.     long long n;
  34.     cin>>n;
  35.     long long m;
  36.     cin>>m;
  37.     long long w[m];
  38.     long long hist[m];
  39.     for(int i=0;i<m;i++){
  40.         cin>>w[i];
  41.         hist[i] = n - w[i];
  42.     }
  43.     cout<<getMaxArea(hist, m);
  44.     return 0;
  45. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top