# CF102920L Two Buildings【分治】【决策单调性】

## Description

There are $n$ buildings along a horizontal street. The buildings are next to each other along the street, and the $i$-th building from left to right has width $1$ and height $h_i$. Among the $n$ buildings, we are to find two buildings, say the $i$-th building and $j$-th building with $i<j$, such that $(h_i+h_j)*(j−i)$ is maximized.

For example, the right figure shows $5$ buildings, with heights $1$, $3$, $2$, $5$, $4$, from left to right. If we choose the first $2$ buildings, then we get $(1+3)*(2−1)=4$. If we choose the first and fifth buildings, then we $(1+4)*(5−1)=20$. The maximum value is achieved by the second and fifth buildings with heights $3$ and $4$, respectively: $(3+4)*(5−2)=21$.

Write a program that, given a sequence of building heights, prints $\max_{1\le i<j\le n}(h_i+h_j)*(j−i)$.

## Input

Your program is to read from standard input. The input starts with a line containing an integer $n$ ($2\le n\le 1,000,000$), where $n$ is the number of buildings. The buildings are numbered $1$ to $n$ from left to right. The second line contains the heights of $n$ buildings separated by a space such that the $i$-th number is the height $h_i$ of the $i$-th building ($1\le h_i\le 1,000,000$).

## Output

Your program is to write to standard output. Print exactly one line. The line should contain $\max_{1\le i<j\le n}(h_i+h_j)*(j−i)$.

## Examples

input

5
1 3 2 5 4


output

21


input

5
8 3 6 3 1


output

36


## 题解：

\begin{aligned}\ [H_i-(-H_j)]\times(j-i)&\geqslant[H_i-(-H_k)]\times(k-i)\\ [H_i-(-H_j)]\times(j-i)\color{red}{-[H_i-(-H_k)]\times(j-i)}&\geqslant[H_i-(-H_k)]\times(k-i)\color{red}{-[H_i-(-H_k)]\times(j-i)}\\ [(-H_k)-(-H_j)]\times(j-i)&\geqslant[H_i-(-H_k)]\times(k-j) \end{aligned}

\begin{aligned}\ [(-H_k)-(-H_j)]\times(j-i)&\geqslant[H_i-(-H_k)]\times(k-j)\\ [(-H_k)-(-H_j)]\times(j-i)\color{blue}{+[(-H_k)-(-H_j)]\times(i-l)}&\geqslant[H_i-(-H_k)]\times(k-j)\color{red}{-(H_i-H_l)\times(k-j)}\\ [(-H_k)-(-H_j)]\times(j-l)&\geqslant[H_l-(-H_k)]\times(k-j)\\ [(-H_k)-(-H_j)]\times(j-l)\color{blue}{+[H_l-(-H_k)]\times(j-l)}&\geqslant[H_l-(-H_k)]\times(k-j)\color{blue}{+[H_l-(-H_k)]\times(j-l)}\\ [H_l-(-H_j)]\times(j-l)&\geqslant[H_l-(-H_k)]\times(k-l) \end{aligned}

## Code：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
int a[1001000],b[1001000],c[1001000];
int bp[1001000],cp[1001000];
ll ans=0;
void solve(int l,int r,int L,int R)
{
if(l>r)
return;
int mid=(l+r)>>1,q=0;
ll Ans=0;
for(int i=L;i<=R;++i)
{
if(Ans<1ll*(cp[i]-bp[mid])*(b[mid]+c[i]))
{
q=i;
Ans=1ll*(cp[i]-bp[mid])*(b[mid]+c[i]);
}
}
ans=ans>Ans?ans:Ans;
solve(l,mid-1,L,q);
solve(mid+1,r,q,R);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int ii=0,iii=0;
c[0]=1e8;
for(int i=1;i<=n;++i)
{
if(a[i]>b[ii])
{
b[++ii]=a[i];
bp[ii]=i;
}

while(a[i]>=c[iii])
--iii;
c[++iii]=a[i];
cp[iii]=i;
}
solve(1,ii,1,iii);
printf("%lld\n",ans);
return 0;
}


### 3 说点什么

0 Followers

Most reacted comment