Submission #1043397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043397		onbert	Salesman (IOI09_salesman)	C++17	40 / 100	569 ms	57168 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5 + 5, maxN = 2e6 + 5;
const ll INF = 1e15;
int n, u, d, s;
vector<pair<int,int>> a[maxn+1];

ll seg[maxN][2];
void build(int id, int l, int r) {
    if (l==r) {
        if (l==s) seg[id][0] = -(l-1) * u, seg[id][1] = -(maxn-l) * d;
        else seg[id][0] = seg[id][1] = -INF;
        return;
    }
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
    seg[id][0] = max(seg[id*2][0], seg[id*2+1][0]);
    seg[id][1] = max(seg[id*2][1], seg[id*2+1][1]);
}
void update(int id, int l, int r, int target, int val) {
    if (r<target || target<l) return;
    if (l==r) {
        seg[id][0] = val - (l-1) * u, seg[id][1] = val - (maxn-l) * d;
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, target, val); update(id*2+1, mid+1, r, target, val);
    seg[id][0] = max(seg[id*2][0], seg[id*2+1][0]);
    seg[id][1] = max(seg[id*2][1], seg[id*2+1][1]);
}
ll qry(int id, int l, int r, int findl, int findr, int j) {
    if (r<findl || findr<l) return -INF;
    if (findl<=l && r<=findr) return seg[id][j];
    int mid = (l+r)/2;
    return max(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
}


signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> u >> d >> s;
    for (int i=1;i<=n;i++) {
        int t, pos, val;
        cin >> t >> pos >> val;
        a[t].push_back({pos, val});
    }
    for (int i=1;i<=maxn;i++) {
        a[i].push_back({0, -INF}); a[i].push_back({maxn+1, -INF});
        sort(a[i].begin(), a[i].end());
    }
    build(1, 1, maxn);
    for (int i=1;i<=maxn;i++) {
        int sz = a[i].size();
        if (sz==2) continue;
        vector<ll> ans0(sz), ans1(sz);
        for (int j=1;j<=sz-2;j++) {
            ll val1 = qry(1, 1, maxn, 1, a[i][j].first, 1) + (maxn-a[i][j].first) * d;
            ll val2 = qry(1, 1, maxn, a[i][j].first, maxn, 0) + (a[i][j].first-1) * u;
            ans0[j] = ans1[j] = max(val1, val2);
        }
        int last = -maxn * d;
        for (int j=1;j<=sz-2;j++) {
            last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
            ans1[j] += last + (maxn-a[i][j].first) * d;
            // cout << last + (maxn-a[i][j].first) * d << endl;
        }
        for (int j=sz-2;j>=1;j--) {
            last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
            ans0[j] += last + (a[i][j].first-1) * u;
        }
        // cout << sz << endl;
        // cout << ans0[1] << " " << ans1[1] << endl;
        // cout << ans0[2] << " " << ans1[2] << endl;
        // cout << ans0[3] << " " << ans1[3] << endl;
        // cout << endl;
        ans1[0] = ans0[sz-1] = -INF;
        for (int j=1;j<=sz-2;j++) ans1[j] = max(ans1[j-1] - (a[i][j].first - a[i][j-1].first) * d + a[i][j].second, ans1[j]);
        for (int j=sz-2;j>=1;j--) ans0[j] = max(ans0[j+1] - (a[i][j+1].first - a[i][j].first) * u + a[i][j].second, ans0[j]);
        for (int j=1;j<=sz-2;j++) update(1, 1, maxn, a[i][j].first, max(ans1[j], ans0[j]));
        // cout << ans0[1] << " " << ans1[1] << endl;
        // cout << ans0[2] << " " << ans1[2] << endl;
        // cout << ans0[3] << " " << ans1[3] << endl;
        // cout << endl;
    }
    ll ans = 0;
    for (int i=1;i<=maxn;i++) {
        ll val = qry(1, 1, maxn, i, i, 0) + (i-1) * u;
        if (i<s) val -= (s-i) * d;
        else val -= (i-s) * u;
        ans = max(val, ans);
    }
    cout << ans << endl;
}

• Subtask 1: 40 / 100