T1为什么95pt?求找错,悬赏1洛谷关注

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define endl '\n'
int n;
int a[2000005];
inline int read(){
	char c = getchar();int x =0;
	while(c<'0' or c>'9')c = getchar();
	while('0'<=c and c<='9')x=  x*10+(c^48),c = getchar();
	return x;
}int ls[2000005],rs[2000005],mx[2000005];
int st[2000005];int head = 1;
__int128 ans = 0;
void write(__int128 x){
	if(x>=10)write(x/10);
	putchar('0'+x%10);return;
}
int rt = 0;
inline int dfs(int x){
	mx[x] = a[x];int len = 1;
	if(ls[x])len+=dfs(ls[x]),mx[x] = max(mx[x],mx[ls[x]]);
	if(rs[x])len+=dfs(rs[x]),mx[x] = max(mx[x],mx[rs[x]]);
	ans = max(ans,(__int128)a[x]*(__int128)mx[x]*(__int128)len);
 //   cout << a[x] << " " << mx[x] << " " << len << endl;
//	cout << x << " " << a[x] << " " << mx[x] << " " << len << endl;
	return len;
}
signed main(){
	n = read();
	for(int i = 1;i<=n;i++)a[i] = read();
	st[1] = 1;
	for(int i= 2;i<=n;i++){
		while(head and a[st[head]]>=a[i])head--;
		if(!head){
			rt = i;ls[i] = st[head+1];
		}else ls[i] = rs[st[head]],rs[st[head]] = i;
		st[++head] = i;
	}
	dfs(rt);write(ans);
    //cout << (long long)ans << endl;
	return 0;
}

全部评论
Cuball
点赞 回复 分享
发布于 2023-10-06 16:14 江西

相关推荐

03-19 10:07
已编辑
门头沟学院 Java
Yki_:你倒是进一个面啊
点赞 评论 收藏
分享
神哥不得了:神哥来啦~1.建议不要包装,很容易问穿2.没日常也能找到暑期3.简历模板换一下,字体和版式看着好难受,而且最好压缩到一页,技术的倒数第2和3重复啦,项目建议换两个高质量的上去,如果时间够的话,八股就把高频top50的题目多巩固几遍,吃透,注意不要找假高频,这样绝对能找到暑期
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务