Submission #300106

#	Time	Username	Problem	Language	Result	Execution time	Memory
300106		tatyam	Salesman (IOI09_salesman)	C++17	100 / 100	1440 ms	52472 KiB

salesman

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

struct SegmentTree{
    ll n, cost;
    vector<ll> seg;
    SegmentTree(ll n, ll cost): n(n), cost(cost), seg(n * 2, -INF){}
    void set(ll at, ll val){
        val += at * cost;
        at += n;
        seg[at] = val;
        while(at /= 2) chmax(seg[at], val);
    }
    ll get(ll l, ll r){
        l += n; r += n;
        ll 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;
    }
    ll down(ll x){
        return get(0, x + 1) - x * cost;
    }
    ll up(ll x){
        return get(x, n) - x * cost;
    }
};
int main(){
    const ll MAX = 500002;
    ll N, U, D, S;
    cin >> N >> U >> D >> S;
    vector<vector<array<ll, 2>>> a(MAX);
    for(ll i = 0; i < N; i++){
        ll 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<ll> dp_up(fairs.size()), dp_down;
        for(ll 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(ll 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(ll 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(ll 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:51:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(ll i = 0; i < fairs.size(); i++) dp_up[i] = max(down.down(fairs[i][0]), up.up(fairs[i][0]));
      |                       ~~^~~~~~~~~~~~~~
salesman.cpp:54:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(ll i = 1; i < fairs.size(); i++){
      |                       ~~^~~~~~~~~~~~~~
salesman.cpp:63:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long int'} and 'std::vector<std::array<long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(ll i = 0; i < fairs.size(); i++){
      |                       ~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100