Submission #1215262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215262		Ariadna	Salesman (IOI09_salesman)	C++20	40 / 100	1405 ms	92400 KiB

salesman

#include <bits/stdc++.h>
using namespace std;

int n, u, d, s;
const int I = 0, F = 500002;

struct Fair {int t, l, m;};  
bool comp(Fair A, Fair B) {return A.t < B.t;}
int price(int a, int b) {return max((b-a)*d, (b-a)*(-u));}

struct Segtree {
    int n;
    vector<int> st;
    Segtree(int n) : n(n), st(vector<int>(4*n, -2e9)) {};

    void update(int p, int l, int r, int i, int x) {
        if (l == r) st[p] = x;
        else {
            int m = (l+r)/2;
            if (i <= m) update(2*p, l, m, i, x);
            else update(2*p+1, m+1, r, i, x);
            st[p] = max(st[2*p], st[2*p+1]);
        }
    }

    int Max(int p, int l, int r, int i, int j) {
        if (i > j) return -2e9;
        else if (i == l && j == r) return st[p];
        int m = (l+r)/2;
        return max(Max(2*p, l, m, i, min(m, j)), Max(2*p+1, m+1, r, max(i, m+1), j));
    }

    void update(int i, int x) {update(1, 0, n-1, i, x);}
    int Max(int i, int j) {return Max(1, 0, n-1, i, j);}
};

map<int, int> cmpr;
map<int, int> inv_cmpr;
void coordinate_compression(vector<Fair>& fairs) {
    set<int> values;
    for (int i = 0; i < n; ++i) values.insert(fairs[i].l);
    int cnt = 0;
    for (int v: values) {
        cmpr[v] = cnt;
        inv_cmpr[cnt] = v;
        ++cnt;
    }
}

signed main() {
    cin >> n >> u >> d >> s;
    vector<Fair> fairs(n);
    for (int i = 0; i < n; ++i) cin >> fairs[i].t >> fairs[i].l >> fairs[i].m;
    sort(fairs.begin(), fairs.end(), comp);
    coordinate_compression(fairs);

    Segtree StU(n), StD(n);

    vector<int> dp(n);
    for (int i = n-1; i >= 0; --i) {
        dp[i] += fairs[i].m;
        int aux = StU.Max(0, cmpr[fairs[i].l]-1)+(F-fairs[i].l)*u;
        aux = max(aux, StD.Max(cmpr[fairs[i].l]+1, n-1)+fairs[i].l*d);
        aux = max(aux, -price(fairs[i].l, s));
        dp[i] += aux;
        
        StU.update(cmpr[fairs[i].l], dp[i]-(F-fairs[i].l)*u);
        StD.update(cmpr[fairs[i].l], dp[i]-fairs[i].l*d);
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) ans = max(ans, dp[i]-price(s, fairs[i].l));
    cout << ans << endl;

    return 0;
}

• Subtask 1: 40 / 100