Submission #445266

#	Time	Username	Problem	Language	Result	Execution time	Memory
445266		qwerasdfzxcl	Salesman (IOI09_salesman)	C++14	100 / 100	997 ms	47416 KiB

salesman

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int MX = 500500;
struct Seg{
    vector<ll> tree;
    int sz;
    void init(int n, vector<ll> &vec){
        sz = n;
        tree.resize(sz*2);
        if (!vec.empty()) for (int i=0;i<sz;i++) tree[i+sz] = vec[i];
        else fill(tree.begin()+sz, tree.begin()+sz*2, -1e18);
        for (int i=sz-1;i;i--) tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void update(int x, ll val){
        for (tree[x+=sz] = val;x>1;x>>=1) tree[x>>1] = max(tree[x], tree[x^1]);
    }
    ll query(int l, int r){
        ll ret = -1e18;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = max(ret, tree[l++]);
            if (r&1) ret = max(ret, tree[--r]);
        }
        return ret;
    }
}tree1, tree2;
vector<pair<int, int>> a[500500];
ll dp[500500];

int main(){
    int n, u, d, s;
    scanf("%d %d %d %d", &n, &d, &u, &s);
    for (int i=0;i<n;i++){
        int t, l, m;
        scanf("%d %d %d", &t, &l, &m);
        a[t].emplace_back(l, m);
    }
    for (int i=1;i<MX;i++) sort(a[i].begin(), a[i].end());
    fill(dp+1, dp+MX, -1e18);
    dp[s] = 0;
    vector<ll> tmp;
    tree1.init(MX, tmp); tree2.init(MX, tmp);
    tree1.update(s, dp[s]-s*d);
    tree2.update(s, dp[s]-(MX-s)*u);

    for (int T=1;T<MX;T++){
        if (a[T].empty()) continue;
        int sz = a[T].size();
        vector<ll> ranL(sz+1, -1e18), ranR(sz+1, -1e18);
        vector<ll> SL(sz), SR(sz);
        SL[0] = a[T][0].second - (u+d)*a[T][0].first;
        SR[sz-1] = a[T][sz-1].second - (u+d)*(MX-a[T][sz-1].first);
        for (int i=1;i<sz;i++) SL[i] = SL[i-1] + a[T][i].second - (u+d)*(a[T][i].first-a[T][i-1].first);
        for (int i=sz-2;i>=0;i--) SR[i] = SR[i+1] + a[T][i].second - (u+d)*(a[T][i+1].first-a[T][i].first);

        vector<ll> TL(sz), TR(sz);
        TL[0] = a[T][0].second - d*(a[T][0].first);
        TR[sz-1] = a[T][sz-1].second - u*(MX-a[T][sz-1].first);
        for (int i=1;i<sz;i++) TL[i] = TL[i-1] + a[T][i].second - d*(a[T][i].first-a[T][i-1].first);
        for (int i=sz-2;i>=0;i--) TR[i] = TR[i+1] + a[T][i].second - u*(a[T][i+1].first-a[T][i].first);

        Seg tree3, tree4;
        tree3.init(sz, SL); tree4.init(sz, SR);
        ll cur1 = 0;
        for (int i=0;i<sz;i++){
            cur1 += a[T][i].second;
            int cur = a[T][i].first+1, nxt = MX;
            if (i!=sz-1) nxt = a[T][i+1].first;
            ll tmp1 = tree1.query(cur, nxt) + (d*(cur-1));
            ll tmp2 = tree2.query(cur, nxt) - (d*(nxt-cur+1)) + (u*(MX-nxt));
            tmp2 += tree3.query(i+1, sz) + (u+d)*nxt - cur1;
            ranL[i] = max(tmp1, tmp2)+TL[i];
            //if (a[T][i].first==75) printf("%lld %lld\n", tmp1, tmp2);
        }
        cur1 = 0;
        for (int i=sz-1;i>=0;i--){
            cur1 += a[T][i].second;
            int cur = a[T][i].first, nxt = 1;
            if (i) nxt = a[T][i-1].first+1;
            ll tmp1 = tree2.query(nxt, cur) + (u*(MX-cur));
            ll tmp2 = tree1.query(nxt, cur) - (u*(cur-nxt+1)) + (d*(nxt-1));
            tmp2 += tree4.query(0, i) + (u+d)*(MX-(nxt-1)) - cur1;
            ranR[i] = max(tmp1, tmp2)+TR[i];
        }

        Seg tree5, tree6;
        tree5.init(sz, ranL); tree6.init(sz, ranR);
        for (int i=0;i<sz;i++){
            int cur = a[T][i].first;
            ll tmp1 = tree5.query(i, sz) - TL[i] + a[T][i].second;
            ll tmp2 = tree6.query(0, i+1) - TR[i] + a[T][i].second;
            dp[cur] = max(tmp1, tmp2);
            tree1.update(cur, dp[cur]-cur*d);
            tree2.update(cur, dp[cur]-(MX-cur)*u);
            //printf("%d: %lld %lld %lld\n", cur, dp[cur], tmp1, tmp2);
        }
    }

    ll ans = 0;
    for (int i=1;i<s;i++) ans = max(ans, dp[i] - u*(s-i));
    for (int i=s+1;i<MX;i++) ans = max(ans, dp[i] - d*(i-s));
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d %d %d", &n, &d, &u, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d %d %d", &t, &l, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100