• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# L – Two Buildings（决策单调性分治 ）2020-2021 ACM-ICPC Asia Seoul Regional Contest

2周前 (05-04) 4次浏览

L – Two Buildings

``````#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
#define ll long long
const ll N=1e6+7;
ll n,a[N],ans;
stack<ll>sa;
vector<ll>ho,aq;
ll cal(ll x,ll y){
ll p=aq[x];
ll P=ho[y];
return (P-p)*(a[P]+a[p]);
}
void gao(ll l,ll r,ll L,ll R){
if(l>r){
return;
}
ll mid=(l+r)/2;
ll p=L;
for(int i=L;i<=R;i++){
if(cal(mid,p)<cal(mid,i)){
p=i;
}
}
ans=max(ans,cal(mid,p));
gao(l,mid-1,L,p);
gao(mid+1,r,p,R);
}
int main(){
ho.push_back(0);
aq.push_back(0);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<=n;i++){
while(!sa.empty()){
ll p=sa.top();
if(a[p]<=a[i]){
sa.pop();
}
else{
break;
}
}
sa.push(i);
}
while(!sa.empty()){
ho.push_back(sa.top());
sa.pop();
}
for(int i=n;i>=1;i--){
while(!sa.empty()){
ll p=sa.top();
if(a[p]<=a[i]){
sa.pop();
}
else{
break;
}
}
sa.push(i);
}
while(!sa.empty()){
aq.push_back(sa.top());
sa.pop();
}
sort(ho.begin(),ho.end());
sort(aq.begin(),aq.end());
gao(1,aq.size()-1,1,ho.size()-1);
printf("%lldn",ans);
}
``````