求调 30pts WA on#1#2#3#4#6#7#8,玄一关
  • 板块P1901 发射站
  • 楼主DPOI
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/14 18:31
  • 上次更新2025/6/15 13:41:59
查看原帖
求调 30pts WA on#1#2#3#4#6#7#8,玄一关
1690315
DPOI楼主2025/6/14 18:31

rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000006],V[1000006];
struct f{
    int num;
    int d;
};
signed main(){
    stack<f>s;
    stack<int>s2;
    int n;cin>>n;
    for (int i=1;i<=n;++i)cin>>a[i]>>V[i];
    for (int i=n;i>=1;--i){
        while (!s.empty()&&s.top().d<=a[i])s.pop();
        if (!s.empty())s2.push((s.top().num));
        else s2.push(0);
        s.push({i,a[i]});
    }
    vector<int>v;
    while (!s2.empty()){
        v.push_back(s2.top());
        s2.pop();
    }
    while (!s.empty())s.pop();
    for (int i=1;i<=n;++i){
        while (!s.empty()&&s.top().d<=a[i])s.pop();
        if (!s.empty())s2.push((s.top().num));
        else s2.push(0);
        s.push({i,a[i]});
    }
    vector<int>v2;
    while (!s2.empty()){
        v2.push_back(s2.top());
        s2.pop();
    }
    int ans[1000006]={0};
    for (int i=1;i<=n;++i){
        if(v[i-1]!=0) ans[v[i-1]]+=V[i];
        if(v2[i-1]!=0) ans[v2[i-1]]+=V[i];
    }
    int maxn=-1e18;
    for (int i=1;i<=n;++i)maxn=max(ans[i],maxn);
    cout<<maxn;
    return 0;
}
2025/6/14 18:31
加载中...