제출 #1139915

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139915		dlguq0107	Salesman (IOI09_salesman)	C++20	30 / 100	667 ms	66952 KiB

salesman

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF=1e18;
const int MAX=500005;

struct Seg{
    ll arr[MAX], seg[4*MAX];

    Seg(){
       for(int i=0; i<MAX; i++) arr[i]=-INF;
       for(int i=0; i<4*MAX; i++) seg[i]=-INF;
    }

    ll query(int l, int r, int nl=0, int nr=MAX-1, int node=1){
        if(r<nl||nr<l) return -INF;
        if(l<=nl&&nr<=r) return seg[node];
        int mid=nl+nr>>1;
        return max(query(l,r,nl,mid,node*2),query(l,r,mid+1,nr,node*2+1));
    }

    ll update(int idx, ll val, int nl=0, int nr=MAX-1, int node=1){
        if(idx<nl||nr<idx) return seg[node];
        if(nl==nr) return seg[node]=val;
        int mid=nl+nr>>1;
        return seg[node]=max(update(idx,val,nl,mid,node*2),update(idx,val,mid+1,nr,node*2+1));
    }
} up, down;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    ll n, u, d, s;
    cin >> n >> u >> d >> s;
    s--;

    vector<vector<pair<ll,ll>>> r(MAX,vector<pair<ll,ll>>()); 
    for(int i=0; i<n; i++){
        ll t, l, m;
        cin >> t >> l >> m;
        r[--t].push_back({--l,m});
    }
    r[MAX-1].push_back({s,0});

    down.update(s,s*d);
    up.update(s,-s*u);
    for(int t=0; t<MAX; t++){
        if(r[t].empty()) continue;
        vector<ll> mx(r[t].size(),-INF);
        sort(r[t].begin(), r[t].end());
        for(auto it=r[t].begin(); it!=r[t].end(); it++){
            auto [l, m] = *it;
            down.update(l,down.query(0,l-1)+m);
        }
        for(auto it=r[t].rbegin(); it!=r[t].rend(); it++){
            auto [l, m] = *it;
            up.update(l,up.query(l+1,MAX-1)+m);
        }
        for(auto [l, m]: r[t]){
            ll mx=max(down.query(l,l)-l*d, up.query(l,l)+l*u);
            down.update(l,mx+l*d);
            up.update(l,mx-l*u);
        }
    }

    cout << max(down.query(0,s-1)-s*d,up.query(s+1,MAX-1)+s*u);
}

• Subtask 1: 30 / 100