Submission #1016279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016279		socpite	Salesman (IOI09_salesman)	C++14	60 / 100	667 ms	65536 KiB

salesman

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

const int maxn = 5e5 + 5;
const long long INF = 1e18;

vector<pair<int, int>> ff[maxn];

int U, D, S, n;

long long st[4*maxn][2];
long long mx[maxn];

void upd(long long val, int pos, int l = 1, int r = maxn - 1, int id = 1){
    if(l == r){
        st[id][0] = val - D*pos;
        st[id][1] = val + U*pos;
    }
    else {
        int mid = (l+r)>>1;
        if(pos <= mid)upd(val, pos, l, mid, id<<1);
        else upd(val, pos, mid+1, r, id<<1|1);
        st[id][0] = max(st[id<<1][0], st[id<<1|1][0]);
        st[id][1] = max(st[id<<1][1], st[id<<1|1][1]);
    }
}

long long gt(int ql, int qr, int ty, int l = 1, int r = maxn - 1, int id = 1){
    if(l > qr || ql > r)return -INF;
    if(ql <= l && r <= qr){
        return st[id][ty];
    }
    int mid = (l+r)>>1;
    return max(gt(ql, qr, ty, l, mid, id<<1), gt(ql, qr, ty, mid+1, r, id<<1|1));
}


int main() {
    cin >> n >> D >> U >> S;
    for(int i = 0; i < 4*maxn; i++)st[i][0] = st[i][1] = -INF;
    for(int i = 0; i < maxn; i++)mx[i] = -INF;

    mx[S] = 0;
    upd(0, S);

    for(int i = 0; i < n; i++){
        int t, l, m;
        cin >> t >> l >> m;
        ff[t].push_back({l, m});
    }
    for(int t = 0; t < maxn; t++){
        auto vec = ff[t];
        int sz = vec.size();
        long long best_back = -INF, best = -INF, sum = 0;
        for(int i = 0; i < sz; i++){
            int prv;
            if(i)prv = vec[i-1].first+1;
            else prv = 1;
            best = max(best, gt(prv, vec[i].first, 1) - sum);
            best_back = max(best_back, -sum + (U+D)*vec[i].first);

            sum += vec[i].second;
            mx[vec[i].first] = max(mx[vec[i].first], best - U*vec[i].first + sum);

            if(i+1 == sz)break;
            int nxt = vec[i+1].first - 1;
            best = max(best, best_back + gt(vec[i].first, nxt, 0));
        }

        best_back = -INF, best = -INF, sum = 0;
        for(int i = sz-1; i >= 0; i--){
            int prv;
            if(i + 1 < sz)prv = vec[i+1].first-1;
            else prv = maxn-1;
            best = max(best, gt(vec[i].first, prv, 0) - sum);
            best_back = max(best_back, -sum - (U+D)*vec[i].first);

            sum += vec[i].second;
            mx[vec[i].first] = max(mx[vec[i].first], best + D*vec[i].first + sum);

            if(!i)break;
            int nxt = vec[i-1].first + 1;
            best = max(best, best_back + gt(nxt, vec[i].first, 1));
        }
        for(auto v: vec){
            upd(mx[v.first], v.first);
        }
    }
    long long ans = -INF;
    for(int i = 0; i < S; i++)ans = max(ans, -U*(S-i) + mx[i]);
    for(int i = S; i < maxn-1; i++)ans = max(ans, -D*(i - S) + mx[i]);
    cout << ans;
}

// 50
// 0 is -D, 1 is +U

• Subtask 1: 60 / 100