Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## WAWAWA!! WHY

Posted by wyzhf99 at 2021-01-10 14:12:52 on Problem 2796
```#include<iostream>
#include<stdio.h>
#include <iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include <stack>
#include<vector>
#include <set>
#include <map>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
int n;
ll sum[100010],a[100010],stk1[100010],stk2[100010],ans_l[100010],ans_r[100010],num1[100010],num2[100010],ss,tt;
int main()
{
sync;
scanf("%d",&n);
sum[0]=0;
for(int i=1;i<=n;++i)
{
//int x=0;
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
//    for(int i=1;i<=n;++i)
//    {
//        cout<<sum[i];//测试一下前缀和
//    }
for(int i=1;i<=n;++i)//
{
ans_r[i]=n;//右边：就是右边没有找到比他小的，就把n作为边界
ans_l[i]=1;//左边：没有找到更小的，就是第一个为边界
}

for(int i=1;i<=n;++i)
{
while(tt&&stk1[tt]>a[i])
{
ans_r[num1[tt]]=i-1;
tt--;
}
stk1[++tt]=a[i];
num1[tt]=i;
}
for(int i=n;i>=1;--i)
{
while(ss&&stk2[ss]>a[i])
{
ans_l[num2[ss]]=i+1;
ss--;
}
stk2[++ss]=a[i];
num2[ss]=i;
}
ll ans=-1,ans__l=0,ans__r=0;
for(int i=1;i<=n;i++)
{
//       cout<<ans_l[i]<<' '<<ans_r[i]<<endl;
int l=ans_l[i],r=ans_r[i];
ll tmp=(sum[r]-sum[l-1])*a[i];
//       cout<<tmp<<endl;
if(tmp>ans)
{
ans=tmp;
ans__l=l;
ans__r=r;
}
}
cout<<ans<<endl;
cout<<ans__l<<' '<<ans__r;
//    int ans=0,ans_l=0,ans_r=0;
//    for(int i=1;i<=n;++i)
//    {
//        {
//            ans=max(ans,(sum[(ans_r[i])]-sum[ans_l[i]-1])*a[i]);
//            ans_l=ans_l[i];
//            ans_r=ans_r[i];
//        }
//    }
//    cout<<ans<<' '<<ans_l<<' '<<ans_r;
return 0;
}
```

Followed by: