AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

AcWing 362. 区间

作者: 作者的头像   Azusamitsusa ,  2023-03-02 19:40:24 ,  所有人可见 ,  阅读 35


0


//郑老师和阿梓一样可爱^_^
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
//const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define db double
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl " \n"
#define all(x) (x).begin(),(x).end()
#define YES {cout<<"YES"<<endl;return;}
#define NO {cout<<"NO"<<endl;return;}
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define fast ios::sync_with_stdio(false);cin.tie(0);
int n,dist[500010];
vector<PII>g[500010];
bool st[500010];
void spfa(){
    queue<int>q;
    q.push(0);
    memset(dist,-0x3f3f,sizeof dist);
    dist[0]=0;
    while(q.size()){
        auto u=q.front();q.pop();
        if(st[u])continue;
        st[u]=true;
        for(auto [v,w]:g[u]){
            if(dist[v]<dist[u]+w){
                dist[v]=dist[u]+w;
                q.push(v);
                st[v]=false;
            }
        }
    }
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a,b,w;cin>>a>>b>>w;
        a++,b++;
        g[a-1].push_back({b,w});
    }
    for(int i=1;i<500010;i++){
        g[i-1].push_back({i,0});
        g[i].push_back({i-1,-1});
    }
    spfa();
    cout<<dist[500001]<<endl;
}
signed main(){
    fast
    int t;t=1;//cin>>t;
    while(t--) {
        //run();
        solve();
    }
    return ~~(0^_^0);
}

0 评论

你确定删除吗?

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息