Submission #374432

#	Time	Username	Problem	Language	Result	Execution time	Memory
374432		jhwest2	Salesman (IOI09_salesman)	C++14	100 / 100	1268 ms	35264 KiB

salesman

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 5e5 + 5;
const lint INF = 4e18;

lint n, u, d, s, Dp[MAX];
pair<plint, lint> A[MAX];

struct SEG {
    lint T[4 * MAX];

    lint init(int lo = 1, int hi = MAX, int idx = 1) {
        if (lo == hi) return T[idx] = -INF;
        return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
    }
    lint update(int a, lint x, int lo = 1, int hi = MAX, int idx = 1) {
        if (a < lo || a > hi) return T[idx];
        if (lo == hi) return T[idx] = x;
        return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
    }
    lint query(int a, int b, int lo = 1, int hi = MAX, int idx = 1) {
        if (b < lo || a > hi) return -INF;
        if (a <= lo && hi <= b) return T[idx];
        return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
    }
} S, T;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> u >> d >> s;
    for (int i = 0; i < n; i++) cin >> A[i].va.va >> A[i].va.vb >> A[i].vb;
    sort(A, A + n);
    S.init(); T.init();
    S.update(s, d * s); T.update(s, -u * s);

    int p = 0;
    for (int day = 1; day < MAX; day++) {
        vector<int> V;
        while (p < n && A[p].va.va == day) V.push_back(p++);
        if (V.empty()) continue;

        vector<plint> Su, Tu;
        for (int x : V) {
            Su.emplace_back(A[x].va.vb, (d + u) * A[x].va.vb + T.query(A[x].va.vb, MAX));
            Tu.emplace_back(A[x].va.vb, -(d + u) * A[x].va.vb + S.query(1, A[x].va.vb));
        }
        for (auto x : Su) S.update(x.va, x.vb);
        for (auto x : Tu) T.update(x.va, x.vb);

        lint mx = S.query(1, A[V[0]].va.vb) + A[V[0]].vb;
        for (int i = 0; i < V.size(); i++) {
            int x = V[i];
            if (i) mx = max(mx, S.query(A[x - 1].va.vb + 1, A[x].va.vb)) + A[x].vb;
            Dp[x] = mx - d * A[x].va.vb;
        }

        mx = T.query(A[V.back()].va.vb, MAX) + A[V.back()].vb;
        for (int i = V.size() - 1; i >= 0; i--) {
            int x = V[i];
            if (i != V.size() - 1) mx = max(mx, T.query(A[x].va.vb, A[x + 1].va.vb - 1)) + A[x].vb;
            Dp[x] = max(Dp[x], mx + u * A[x].va.vb);
        }

        for (int x : V) {
            S.update(A[x].va.vb, Dp[x] + d * A[x].va.vb);
            T.update(A[x].va.vb, Dp[x] - u * A[x].va.vb);
        }
    }

    lint ans = 0;
    for (int i = 0; i < n; i++) {
        if (A[i].va.vb > s) ans = max(ans, Dp[i] - u * (A[i].va.vb - s));
        else ans = max(ans, Dp[i] - d * (s - A[i].va.vb));
    }
    cout << ans;
}

Compilation message (stderr)

salesman.cpp: In member function 'lint SEG::init(int, int, int)':
salesman.cpp:22:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                      ~~~^~~~
salesman.cpp:22:75: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                                                        ~~~^~~~
salesman.cpp: In member function 'lint SEG::update(int, lint, int, int, int)':
salesman.cpp:27:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                              ~~~^~~~
salesman.cpp:27:91: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                                                                        ~~~^~~~
salesman.cpp: In member function 'lint SEG::query(int, int, int, int, int)':
salesman.cpp:32:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                    ~~~^~~~
salesman.cpp:32:80: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                                                             ~~~^~~~
salesman.cpp: In function 'int main()':
salesman.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i = 0; i < V.size(); i++) {
      |                         ~~^~~~~~~~~~
salesman.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             if (i != V.size() - 1) mx = max(mx, T.query(A[x].va.vb, A[x + 1].va.vb - 1)) + A[x].vb;
      |                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100