Submission #1156804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156804		Doncho_Bonboncho	Salesman (IOI09_salesman)	C++20	100 / 100	397 ms	49684 KiB

salesman

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define out(x) #x << " = " << x << "  "
#define endl "\n"
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
typedef long long ll;
#define int ll
const ll mod = 1e9 + 7;
const ll inf = 1e17;
const int MAX_N = 5e5 + 42;
const ll neutr = -inf;
struct SegmentTree {
    vector<ll> tree;
    void build() { tree.resize(4 * MAX_N, neutr); }
    void set(int ind, ll val, int x = 1, int lx = 0, int rx = MAX_N) {
        if(lx == rx) { chkmax(tree[x], val); return; }
        int m = (lx + rx) >> 1;
        if(ind <= m) set(ind, val, 2*x, lx, m);
        else set(ind, val, 2*x+1, m+1, rx);
        tree[x] = max(tree[2*x], tree[2*x+1]);
    }
    ll query(int l, int r, int x = 1, int lx = 0, int rx = MAX_N) {
        if(l > rx || lx > r) return neutr;
        if(l <= lx && rx <= r) return tree[x];
        int m = (lx + rx) >> 1;
        ll left = query(l, r, 2*x, lx, m);
        ll right = query(l, r, 2*x+1, m+1, rx);
        return max(left, right);
    }
};
SegmentTree segUp, segDown;
vector<pair<int, pair<int, int>>> v;
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, U, D, L; cin >> n >> U >> D >> L;
    for(int i = 1; i <= n; i++){
        int t, l, c; cin >> t >> l >> c;
        v.push_back({t, {l, c}});
    }
    v.push_back({-1, {L, 0}});
    v.push_back({mod, {L, 0}});
    sort(v.begin(), v.end());
    segUp.build(); segDown.build();
    vector<ll> dp(MAX_N, neutr);
    dp[L] = 0;
    segUp.set(L, -L * U + dp[L]);
    segDown.set(L, L * D + dp[L]);
    for(int i = 1; i < (int)v.size(); ){
        int currInd = i;
        while(currInd < (int)v.size() && v[currInd].first == v[i].first) currInd++;
        int cnt = currInd - i;
        vector<int> pos(cnt);
        vector<ll> base(cnt), fwd(cnt), bwd(cnt);
        for(int k = 0; k < cnt; k++){
            int p = v[i+k].second.first;
            pos[k] = p;
            ll cand1 = segUp.query(p, MAX_N - 1) + p * U;
            ll cand2 = segDown.query(0, p) - p * D;
            base[k] = max(cand1, cand2);
        }
        fwd[0] = base[0] + v[i].second.second;
        for(int k = 1; k < cnt; k++){
            fwd[k] = max(base[k] + v[i+k].second.second, fwd[k-1] - D * (pos[k] - pos[k-1]) + v[i+k].second.second);
        }
        bwd[cnt-1] = base[cnt-1] + v[i+cnt-1].second.second;
        for(int k = cnt - 2; k >= 0; k--){
            bwd[k] = max(base[k] + v[i+k].second.second, bwd[k+1] - U * (pos[k+1] - pos[k]) + v[i+k].second.second);
        }
        for(int k = 0; k < cnt; k++){
            int p = pos[k];
            ll newVal = max(fwd[k], bwd[k]);
            if(newVal > dp[p]){
                dp[p] = newVal;
                segUp.set(p, dp[p] - p * U);
                segDown.set(p, dp[p] + p * D);
            }
        }
        i = currInd;
    }
    cout << dp[L] << endl;
    return 0;
}

• Subtask 1: 100 / 100