ac

我是小学生  •  10天前


include <bits/stdc++.h>

using namespace std; typedef long long ll;

struct node {

ll h, v, sum = 0;

} a[1000010];

int main() {

ll n, maxn = 0;
cin >> n;
for (ll i = 1; i <= n; i++) {
	cin >> a[i].h >> a[i].v;
}
stack<ll> st;
for (ll i = 1; i <= n; i++) {
	while (!st.empty() && a[st.top()].h <= a[i].h) {
		st.pop();
	}
	if (!st.empty()) {
		a[st.top()].sum += a[i].v;
	}
	st.push(i);
}

while (!st.empty())
	st.pop();
for (ll i = n; i >= 1; i--) {
	while (!st.empty() && a[st.top()].h <= a[i].h) {
		st.pop();
	}
	if (!st.empty()) {
		a[st.top()].sum += a[i].v;
	}
	st.push(i);
}

for (ll i = 1; i <= n; i++) {
	maxn = max(a[i].sum, maxn);
}
cout << maxn;
return 0;

}


评论:

请先登录,才能进行评论