Submission #1156787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156787		Doncho_Bonboncho	Salesman (IOI09_salesman)	C++20	0 / 100	712 ms	47584 KiB

salesman

#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
#include <random>
#include <utility>
#include <variant>
#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; }
template<class T, class T2>
inline bool chkmin(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 {
    std::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) {
            cerr << out(lx) << out(ind) << out(val) << endl;
            chkmax(tree[x], val);
            cerr << out(tree[x]) << endl;
            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] = std::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 and 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 std::max(left, right);
    }
};

SegmentTree segUp;
SegmentTree segDown;

std::vector< std::pair< int, std::pair< int, int > > > v;
signed main(){
#ifndef LOCAL
    std::ios_base::sync_with_stdio(false); 
    std::cin.tie(NULL); 
    std::cout.tie(NULL);
#endif

    int n, U, D, L;
    std::cin >> n >> U >> D >> L;

    for(int i = 1; i <= n; i++){
        int t, l, c;
        std::cin >> t >> l >> c;
        v.push_back({t, {l, c}});
    }
    // Add dummy fairs for the starting and ending conditions.
    v.push_back({ -1, { L, 0 } });
    v.push_back({ mod, { L, 0 } });

    std::sort(v.begin(), v.end());

    segUp.build();
    segDown.build();

    std::vector<ll> dp(MAX_N, neutr);
    dp[L] = 0;
    segUp.set(L, -L * U + dp[L]);
    segDown.set(L, L * D + dp[L]);

    cerr << out(segUp.tree[1]) << endl;
    cerr << out(segDown.tree[1]) << endl;

    // Process fairs day by day (all fairs on the same day are consecutive)
    for(int i = 1; i < (int)v.size(); i++){
        int currInd = i;
        while(currInd < (int)v.size() && v[currInd].first == v[i].first){
            currInd++;
        }

        // Forward pass: update each fair immediately so its profit is available to subsequent fairs.
        for(int j = i; j < currInd; j++){
            int currPos = v[j].second.first;
            ll maxUp = segUp.query(currPos, MAX_N - 1) + currPos * U;
            ll maxDown = segDown.query(0, currPos) - currPos * D;
            ll best = max(maxUp, maxDown);
            // Immediately add the fair's profit.
            chkmax(dp[currPos], best + v[j].second.second);
            // Update segment trees immediately.
            segUp.set(currPos, -currPos * U + dp[currPos]);
            segDown.set(currPos, currPos * D + dp[currPos]);
        }
        
        // Backward pass: to ensure optimal transitions in the reverse order for fairs on the same day.
        for(int j = currInd - 1; j >= i; j--){
            int currPos = v[j].second.first;
            ll maxUp = segUp.query(currPos, MAX_N - 1) + currPos * U;
            ll maxDown = segDown.query(0, currPos) - currPos * D;
            ll best = max(maxUp, maxDown);
            chkmax(dp[currPos], best + v[j].second.second);
            segUp.set(currPos, -currPos * U + dp[currPos]);
            segDown.set(currPos, currPos * D + dp[currPos]);
        }
        
        i = currInd - 1;
    }

    std::cout << dp[L] << endl;
    return 0;
}

• Subtask 1: 0 / 100