123

Gooooogle  •  11个月前


#include<bits/stdc++.h>
using namespace std;
long long sta[1000100];//栈中存坐标 
long long sum[1000100];
long long h[1000100];
long long v[1000100];
int main(){
	int n;
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&h[i],&v[i]);
		if(h[sta[ans]]>h[i]){
			if(ans>=1) sum[sta[ans]]+=v[i];//进栈元素前一个元素要加上这个进栈元素的值 
			sta[++ans]=i;//入栈 
		}
		else{//出栈 
			while(ans&&h[sta[ans]]<h[i]){
				sum[i]+=v[sta[ans]];//出栈元素的值要全部加起来给要进栈的元素 
				ans--;
			}
			if(ans>=1) sum[sta[ans]]+=v[i];//同上 
			sta[++ans]=i; 
		} 
	}
	long long Max=0;
	for(int i=1;i<=n;i++){
		Max=max(Max,sum[i]);
	}
	printf("%lld\n",Max);
	return 0;
} 

评论:

请先登录,才能进行评论