Submission #1267854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267854		nguyenvietanh	Salesman (IOI09_salesman)	C++20	65 / 100	631 ms	63060 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define inp(name) freopen(name, "r", stdin);
#define out(name) freopen(name, "w", stdout);

const int N = 5e5 + 10;
const int mod = 998244353;
int n, U, D, s;
int dp[N], sum[N], suffix[N], prefix[N];
int new_dp[N];
struct vanhdepchai{
    int t, l, m;
} a[N];
bool operator < (vanhdepchai a, vanhdepchai b){
    if (a.t == b.t) return a.l < b.l;
    return a.t < b.t;
}

struct segtree{
    int n;
    vector <int> st;
    segtree(int _n){
        n = _n;
        st.assign(4 * n + 5, -4e18);
    }
    void update(int node, int l, int r, int pos, int v){
        if (l > pos || r < pos) return;
        if (l == r){
            st[node] = max(st[node], v); return;
        }
        int mid = (l + r)/2;
        update(node * 2, l, mid, pos, v);
        update(node * 2 + 1, mid + 1, r, pos, v);
        st[node] = max(st[node * 2], st[node * 2 + 1]);
    }
    void update(int pos, int v){
        update(1, 1, n, pos, v);
    }
    int get(int node, int l, int r, int lf, int rt){
        if (l > rt || r < lf) return -4e18;
        if (lf <= l && r <= rt) return st[node];
        int mid = (l + r)/2;
        return max(get(node * 2, l, mid, lf, rt), get(node * 2 + 1, mid + 1, r, lf, rt));
    }
    int get(int l, int r){
        if (l > r) return -4e18;
        return get(1, 1, n, l, r);
    }
};
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> U >> D >> s;
    int mx = s;
    for (int i = 1; i <= n; i ++){
        cin >> a[i].t >> a[i].l >> a[i].m;
        mx = max(mx, a[i].l);
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++) sum[i] = sum[i - 1] + a[i].m;
    segtree u(mx + 5), d(mx + 5);
    u.update(s, s * D);
    d.update(s, -s * U);
    int l = 1, r = 1;
    int ans = 0;
    while (l <= n){
        while (r <= n && a[l].t == a[r].t) r ++;
        r --;;
        prefix[l - 1] = suffix[r + 1] = -4e18;
        for (int i = l; i <= r; i ++){
            dp[i] = u.get(1, a[i].l - 1) - a[i].l * D + a[i].m;
            dp[i] = max(dp[i], d.get(a[i].l + 1, mx) + a[i].l * U + a[i].m);
            prefix[i] = max(prefix[i - 1], a[i].l * (U + D) - sum[i - 1]);
            new_dp[i] = -2e18;
        }
        for (int i = r; i >= l; i --){
            suffix[i] = max(suffix[i + 1], sum[i] - a[i].l * (U + D));
        }
        int pre = dp[l];
        new_dp[l] = dp[l] + max(1ll*0, suffix[l] - sum[l] + a[l].l * (U + D));
        for (int i = l + 1; i <= r; i ++){
            pre = max(dp[i], pre - (a[i].l - a[i - 1].l) * D + a[i].m);
            new_dp[i] = pre + max(1ll * 0, suffix[i] - sum[i] + a[i].l * (U + D));
        }
        pre = dp[r];
        new_dp[r] = max(new_dp[r], dp[r] + max(1ll * 0, prefix[r] - a[r].l * (U + D) + sum[r - 1]));
        for (int i = r - 1; i >= l; i --){
            pre = max(dp[i], pre - (a[i + 1].l - a[i].l) * U + a[i].m);
            new_dp[i] = pre + max(1ll * 0, prefix[i] - a[i].l * (U + D) + sum[i - 1]);
        }
        for (int i = l; i <= r; i ++){
            dp[i] = max(dp[i], new_dp[i]);
            if (a[i].l > s){
                ans = max(ans, -(a[i].l - s) * U + dp[i]);
            }
            else ans = max(ans, -(s - a[i].l) * D + dp[i]);
            u.update(a[i].l, dp[i] + a[i].l * D);
            d.update(a[i].l, dp[i] - a[i].l * U);
        }
        l = r = r + 1;
    }
    cout << ans;
}

• Subtask 1: 65 / 100