比赛 20241022 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 电梯 最终得分 100
用户昵称 wdsjl 运行时间 0.326 s
代码语言 C++ 内存使用 4.06 MiB
提交时间 2024-10-22 11:32:55
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;

const int N = 100005;

int n,stk[N],top;
long long t[N],h[N];
long long now;

int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	scanf("%d%d",&t[i],&h[i]);
	for(int i=1;i<=n;i++){
		while(top&&h[i]>h[stk[top]]) top--;
		stk[++top]=i;
	}
	for(int i=1;i<=top;i++){
		int pre=h[stk[i]];
		if(t[stk[i]]<=now){
			while(t[stk[i]]<=now&&i<=top) i++;
			i--;
		}
		t[stk[i]]=max(now,t[stk[i]]);
		h[stk[i]]=pre;
		int x=stk[i];
		int y=stk[i+1];
		while(max(t[y],max(t[x],now)+h[x]+h[x])+h[y]+h[y]>max(t[y],now)+h[x]+h[x]&&i<top){
			h[y]=h[x];
			i++;
			x=stk[i];
			y=stk[i+1];
		}
		now=max(now,t[x]+h[x]+h[x]);
	}
	cout<<now;
	return 0;
}