Submission #300113

#	Time	Username	Problem	Language	Result	Execution time	Memory
300113		tatyam	Salesman (IOI09_salesman)	C++17	100 / 100	1410 ms	35656 KiB

salesman

#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;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0; i < fairs.size(); i++) dp_up[i] = max(down.down(fairs[i][0]), up.up(fairs[i][0]));
      |                        ~~^~~~~~~~~~~~~~
salesman.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i = 1; i < fairs.size(); i++){
      |                        ~~^~~~~~~~~~~~~~
salesman.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i = 0; i < fairs.size(); i++){
      |                        ~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100