fork(1) download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct s{
  6.     int sum,xs;
  7.     int lsum,rsum,x1,x2;
  8.     int maxarr;
  9. } tree[300000]={0};
  10. void merge(int ind)
  11. {
  12.     s l,r;
  13.     l= tree[2*ind+1];
  14.     r= tree[2*ind+2];
  15.  
  16.    int a= max(l.lsum*l.x1,(l.sum+r.lsum)*(l.xs+r.x1));
  17.     if(a==l.sum*l.x1)
  18.     {
  19.         tree[ind].lsum= l.lsum;
  20.         tree[ind].x1= l.x1;
  21.     }
  22.     else {tree[ind].lsum= l.sum+r.lsum;
  23.     tree[ind].x1=(l.xs+r.x1);
  24.     }
  25.  
  26.     int b= max(r.rsum*r.x2,(l.rsum+r.sum)*(r.xs+l.x2));
  27.     if(b==r.rsum*r.x2)
  28.     {
  29.         tree[ind].rsum= r.rsum;
  30.         tree[ind].x2= r.x2;
  31.     }
  32.     else{
  33.         tree[ind].rsum= l.rsum+ r.sum;
  34.         tree[ind].x2= r.xs+l.x2;
  35.     }
  36.  
  37.     tree[ind].sum= l.sum+r.sum;
  38.     tree[ind].xs= l.xs+r.xs;
  39.  
  40.     tree[ind].maxarr= max(tree[2*ind+1].maxarr,max(tree[2*ind+2].maxarr,(l.rsum+r.lsum)*(l.x2+r.x1)));
  41.  
  42. }
  43. void build(int st,int en,int ind,int *arr)
  44. {
  45.     int mid= (st+en)/2;
  46.     if(st==en)
  47.     {
  48.         tree[ind].maxarr=tree[ind].rsum=tree[ind].lsum=tree[ind].sum= arr[st];
  49.         tree[ind].x1=tree[ind].x2=tree[ind].xs=1;
  50.         return;
  51.     }
  52.     build(st,mid,2*ind+1,arr);
  53.     build(mid+1,en,2*ind+2,arr);
  54.     merge(ind);
  55. }
  56. int main()
  57. {
  58.     int n;
  59.     cin>>n;
  60.     int arr[100000];
  61.     for(int i=0;i<n;i++)cin>>arr[i];
  62.     build(0,n-1,0,arr);
  63.     //for(int i=0;i<2*n-1;i++)cout<<tree[i].maxarr<<" ";cout<<endl;
  64.     cout<<tree[0].maxarr<<endl;
  65.     return 0;
  66. }
  67.  
Runtime error #stdin #stdout 0s 19720KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/BmIcs3
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!