30pts WA 求调,玄关
  • 板块P1901 发射站
  • 楼主DPOI
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/6/29 09:37
  • 上次更新2025/6/29 20:20:26
查看原帖
30pts WA 求调,玄关
1690315
DPOI楼主2025/6/29 09:37
#include<bits/stdc++.h>
using namespace std;
int a[1000006],V[1000006];
struct f{
    int num;
    int d;
};
int 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])ans[v[i-1]]+=V[i];
        if(v2[i-1])ans[v2[i-1]]+=V[i];
    }
    
    int maxn=0;
    for (int i=1;i<=n;++i)if(ans[i]>maxn)maxn=ans[i];
    cout<<maxn;
    return 0;
}
2025/6/29 09:37
加载中...