C++14(g++5.4) 解法, 执行用时: 220ms, 内存消耗: 23816K, 提交时间: 2019-04-14 19:23:33

#include<bits/stdc++.h>
#define MAXN 1000000
using namespace std;
typedef long long ll;
ll h[MAXN+5],w[MAXN+5];
ll pre[MAXN+5];
int main()
{
	ios::sync_with_stdio(false);
	ll N;
	cin>>N;
	for(int i=1;i<=N;++i){
		cin>>w[i];
		pre[i]=pre[i-1]+w[i];	
	} 
	for(int i=1;i<=N;++i) cin>>h[i];
	stack<int> sta;
	sta.push(0);
	ll ans=0;
	for(int i=1;i<=N+1;++i){
		while(h[i]<h[sta.top()]){
			ll ans1=h[sta.top()];
			sta.pop();
			ll ans2=pre[i-1]-pre[sta.top()];
			ans=max(ans,ans1*ans2);
		}
		sta.push(i);
	}
	cout<<ans<<endl;
}

C 解法, 执行用时: 181ms, 内存消耗: 15912K, 提交时间: 2022-08-04 13:37:08

#include<stdio.h>
long long q[1000005];
long long sum[1000005];
long long a[1000005];
int main()
{
	int i,j,k,l,n,m,p=0;
	long long max=-1;
	scanf("%d",&n);
	sum[0]=0;q[0]=0;a[0]=-1;a[n+1]=-1;
	for(i=1;i<=n;i++){
	scanf("%d",&k);sum[i]=sum[i-1]+k;}
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	q[++p]=1;
	for(i=2;i<=n+1;i++)
	if(a[i]>=a[q[p]]){
		q[++p]=i;
	}
	else{
		while(a[q[p]]>a[i]){
			if(a[q[p]]*(sum[i-1]-sum[q[p-1]])>max)max=a[q[p]]*(sum[i-1]-sum[q[p-1]]);
			p--;
		}
		q[++p]=i;
	}
	printf("%lld",max);
}

C++11(clang++ 3.9) 解法, 执行用时: 692ms, 内存消耗: 15964K, 提交时间: 2019-04-14 14:12:38

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;


ll a[maxn],h[maxn];


int main()
{
	ll n,ans=0;
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		a[i]+=a[i-1];
	}
	for(int i=1; i<=n; i++)
		cin>>h[i];
	stack <int> s;
	s.push(0);
	for(int i=1; i<=n; i++)
	{
		while(h[i]<h[s.top()])
		{
			int t1=s.top();
			s.pop();
			int t2=s.top();
			ans=max(ans,h[t1]*(a[i-1]-a[t2]));
		}
		s.push(i);
	}
	cout<<ans<<endl;
}

Python3 解法, 执行用时: 1693ms, 内存消耗: 173204K, 提交时间: 2022-08-05 12:09:23

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    a[i] += a[i - 1]
b = list(map(int,input().split()))
res,tt = 0,0
stk = [0] * 1000005
for i in range(n):
    while tt > 0 and b[stk[tt]] > b[i]:
        res = max(res,b[stk[tt]] * (a[i - 1] - a[stk[tt - 1]]))
        tt -= 1
    tt += 1
    stk[tt] = i
print (res)