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;
}
评论:
请先登录,才能进行评论