fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4.  
  5. #define ull long long int
  6. using namespace std;
  7.  
  8. const int MAX=100005;
  9. ull ARR[MAX],maxi;      //to be set to -1
  10.  
  11. void M(int lo,int m,int hi){
  12.     int i=m,j=m+1;
  13.     ull mini=min(ARR[i],ARR[j]);
  14.     bool f=1;
  15.     while(i>=lo && j<=hi && f){
  16.         if(maxi<=((ull)(j-i+1))*mini){
  17.             maxi=(j-i+1)*mini;
  18.         }
  19.         if(i>lo&&ARR[i-1]>=mini){
  20.             i-=1;
  21.         }
  22.         else if(j<hi && ARR[j+1]>=mini){
  23.             j+=1;
  24.         }
  25.         else{
  26.             if(i>lo){
  27.                 i-=1;
  28.                 mini=min(mini,ARR[i]);
  29.             }
  30.             else if(j<hi){
  31.                 j+=1;
  32.                 mini=min(mini,ARR[j]);
  33.             }
  34.             else if(i>=lo && j<=hi)
  35.                 f=0;
  36.         }
  37.     }
  38. }
  39.  
  40. void DnC(int lo,int hi){
  41.     if(lo>=hi)
  42.         return;
  43.  
  44.     int mid=lo + (hi-lo)/2;
  45.     DnC(lo,mid);
  46.     DnC(mid+1,hi);
  47.     M(lo,mid,hi);
  48. }
  49.  
  50. int main(){
  51.     int N,z;
  52.     while(1){
  53.         scanf("%d",&N);
  54.         if(N==0)
  55.             break;
  56.         for(z=0;z<N;z++){
  57.             scanf("%lld",&ARR[z]);
  58.         }
  59.         maxi=-1;
  60.         //cout<<N<<endl;
  61.         DnC(0,N-1);
  62.  
  63.         for(z=0;z<N;z++){           //to compare individual value with maxi
  64.             if(ARR[z]>maxi)
  65.                 maxi=ARR[z];
  66.         }
  67.         printf("%lld\n",maxi);
  68.     }
  69.  
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 4244KB
comments (?)
stdin
copy 
7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
5 1 2 3 4 5
4 1 9 1 1
0
stdout
copy 
8
4000
9
9
https://ideone.com/hf0FuB
language:
C++14 (gcc 8.3)
created:
8 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!