---
tags: IOI
---
# IOI2009 Day2-4 旅するセールスマン (Salesman)

## 問題

https://www.ioi-jp.org/ioi/2009/problems/day2/Salesman_jp.pdf
https://oj.uz/problem/view/IOI09_salesman

川沿いで $N$ 個の展示即売会が開催されます。 $i$ 番目の展示即売会は $T_i$ 日に、川の上流からの位置 $L_i$ で開催され、参加すると $M_i$ の利益を得ます。
同じ日に開催される複数の展示即売会に参加することができます。
川を $1$ 上るにはコストが $U$ かかり、川を $1$ 下るにはコストが $D$ かかります。
位置 $S$ から始めて $S$ に帰るルートをうまく選んだとき、利益の合計の最大値を求めてください。

$N ≤ 5 \times 10^5$
$L ≤ 5 \times 10^5$

## 考察

$dp[i]=$ (位置 $i$ にいるときのコストの最小値) を考える。
上る場合は $dp[i]-U*i$ 、下る場合は $dp[i]+D*i$ の RMQ を持っておくと、任意の場所に行くときのコストの最小値がわかる。
あとは同じ日に複数の展示即売会が開催される場合。
上ってから下る場合と、下ってから上る場合があるので、全ての展示即売会に行くコストを求めたあと、上りと下り別々に更新する。

## 実装

https://oj.uz/submission/300113

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
template<class T> bool chmax(T& a, const T& b){ if(a < b){ a = b; return 1; } return 0; }


struct SegmentTree{
    int n, cost;
    vector<int> seg;
    SegmentTree(int n, int cost): n(n), cost(cost), seg(n * 2, -INF){}
    void set(int at, int val){
        val += at * cost;
        at += n;
        seg[at] = val;
        while(at /= 2) chmax(seg[at], val);
    }
    int get(int l, int r){
        l += n; r += n;
        int ans = -INF;
        while(l < r){
            if(l & 1) chmax(ans, seg[l++]);
            if(r & 1) chmax(ans, seg[--r]);
            l /= 2;
            r /= 2;
        }
        return ans;
    }
    int down(int x){
        return get(0, x + 1) - x * cost;
    }
    int up(int x){
        return get(x, n) - x * cost;
    }
};

int main(){
    const int MAX = 500002;
    
    int N, U, D, S;
    cin >> N >> U >> D >> S;
    
    vector<vector<array<int, 2>>> a(MAX);
    for(int i = 0; i < N; i++){
        int T, L, M;
        cin >> T >> L >> M;
        a[T].push_back({L, M});
    }
    
    SegmentTree up(MAX, -U), down(MAX, D);
    up.set(S, 0);
    down.set(S, 0);
    
    for(auto& fairs : a) if(fairs.size()){
        sort(fairs.begin(), fairs.end());
        
        vector<int> dp_up(fairs.size()), dp_down;
        for(int i = 0; i < fairs.size(); i++) dp_up[i] = max(down.down(fairs[i][0]), up.up(fairs[i][0]));
        dp_down = dp_up;
        
        dp_down[0] += fairs[0][1];
        for(int i = 1; i < fairs.size(); i++){
            chmax(dp_down[i], dp_down[i - 1] - D * (fairs[i][0] - fairs[i - 1][0]));
            dp_down[i] += fairs[i][1];
        }
        dp_up.back() += fairs.back()[1];
        for(int i = fairs.size() - 1; i--; ){
            chmax(dp_up[i], dp_up[i + 1] - U * (fairs[i + 1][0] - fairs[i][0]));
            dp_up[i] += fairs[i][1];
        }
        
        for(int i = 0; i < fairs.size(); i++){
            up.set(fairs[i][0], max(dp_up[i], dp_down[i]));
            down.set(fairs[i][0], max(dp_up[i], dp_down[i]));
        }
    }
    
    cout << max(up.up(S), down.down(S)) << endl;
}