Submission #119780

#	Time	Username	Problem	Language	Result	Execution time	Memory
119780		win11905	Salesman (IOI09_salesman)	C++11	40 / 100	1081 ms	65536 KiB

salesman

#include <bits/stdc++.h>
#define long long long
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const long INF = 1e10;

const int N = 1<<19;

int n, u, d, s;
long t1[N<<1], t2[N<<1];

void update(long t[], int x, long v) {
    x += N;
    for(t[x] = max(t[x], v); x != 1; x >>= 1) t[x>>1] = max(t[x], t[x^1]);
}

long query(long t[], int l, int r) {
    long mx = -INF;
    for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
        if(l & 1) mx = max(mx, t[l++]);
        if(r & 1) mx = max(mx, t[--r]);
    }
    return mx;
}

long p;

void updcost(long a, long b) {
    update(t1, a, b - p * a);
    update(t2, a, b + p * a);
}

long getcost(long a) {
    long vl = (query(t1, a, N-1) + p * a);
    long vr = (query(t2, 0, a) - p * a);
    return max(vl, vr);
}

int main() {
    fill_n(t1, N<<1, -INF);
    fill_n(t2, N<<1, -INF);
    scanf("%d %d %d %d", &n, &u, &d, &s);
    map<int, vector<pii>> Mp;
    p = u+d;
    for(int i = 0, a, b, c; i < n; ++i) {
        scanf("%d %d %d", &a, &b, &c);
        Mp[a].emplace_back(b, c << 1);
    }
    updcost(s, 0);
    for(auto &x : Mp) {
        vector<pii> &now = x.y;
        int n = now.size();
        sort(all(now));
        vector<long> dp1, dp2, pref, suff, cost;
        for(auto z : now) {
            cost.emplace_back(getcost(z.x) + z.y);
            // cerr << query(t1, z.x, N-1) << " = " << query(t2, 0, z.x) << " -> " << cost.back() << endl;
        }
        dp1.emplace_back(now[0].y), pref.emplace_back(now[0].y);
        for(int i = 1; i < n; ++i) {
            dp1.emplace_back(max(dp1.back() - 2 * p * (now[i].x - now[i-1].x), 0ll) + now[i].y); 
            pref.emplace_back(pref.back() + now[i].y + p * (now[i].x - now[i-1].x));
        }
        reverse(all(now));
        dp2.emplace_back(now[0].y), suff.emplace_back(now[0].y);
        for(int i = 1; i < n; ++i) {
            dp2.emplace_back(max(dp2.back() - 2 * p * (now[i-1].x - now[i].x), 0ll) + now[i].y); 
            suff.emplace_back(suff.back() + now[i].y + p * (now[i-1].x - now[i].x));
        }
        reverse(all(now)), reverse(all(dp2)), reverse(all(suff));
        long premax = -INF;
        for(int i = 0; i < n; ++i) {
            cost[i] = max(cost[i], dp2[i] - now[i].y + pref[i] + premax);
            premax = max(premax, dp1[i] - pref[i] + getcost(now[i].x));
        }
        premax = -INF;
        for(int i = n-1; i >= 0; --i) {
            cost[i] = max(cost[i], dp1[i] - now[i].y + suff[i] + premax);
            premax = max(premax, dp2[i] - suff[i] + getcost(now[i].x));
        }
        for(int i = 0; i < n; ++i) {
            // cerr << x.x << " " << now[i].x << " -> " << now[i].y << " => " << cost[i] << endl;
            updcost(now[i].x, cost[i]);
        }
    }
    long ansl = query(t1, s, N-1) + p * s;
    long ansr = query(t2, 0, s) - p * s;
    printf("%lld\n", max(ansl, ansr) >> 1);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &n, &u, &d, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 40 / 100