oj.uz

답안 #637735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637735 2022-09-03T00:35:25 Z skittles1412 Salesman (IOI09_salesman) C++17
100 / 100
 679 ms 53708 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

constexpr int maxn = 1 << 19;

struct ST {
    long v[maxn << 1];

    ST() {
        fill(begin(v), end(v), -1e18);
    }

    void update(int o, int l, int r, int ind, long x) {
        if (l == r) {
            v[o] = x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ind <= mid) {
            update(lc, l, mid, ind, x);
        } else {
            update(rc, mid + 1, r, ind, x);
        }
        v[o] = max(v[lc], v[rc]);
    }

    void update(int ind, long x) {
        update(1, 0, maxn - 1, ind, x);
    }

    long query(int o, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) {
            return v[o];
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        long ans = -1e18;
        if (ql <= mid) {
            ans = max(ans, query(lc, l, mid, ql, qr));
        }
        if (mid < qr) {
            ans = max(ans, query(rc, mid + 1, r, ql, qr));
        }
        return ans;
    }

    long query(int l, int r) const {
        return query(1, 0, maxn - 1, l, r);
    }
} lst, rst;

void solve() {
    int n, u, d, s;
    cin >> n >> u >> d >> s;
    vector<pair<int, int>> arr[maxn];
    for (int i = 0; i < n; i++) {
        int t, l, c;
        cin >> t >> l >> c;
        arr[t].emplace_back(l, c);
    }
    lst.update(s, s * d);
    rst.update(s, -s * u);
    arr[maxn - 1].emplace_back(s, 0);
    for (auto& a : arr) {
        if (!sz(a)) {
            continue;
        }
        sort(begin(a), end(a));
        int m = sz(a);
        long opt[m], mval[m];
        fill(opt, opt + m, -1e18);
        fill(mval, mval + m, -1e18);
        for (int i = 0; i < m; i++) {
            mval[i] =
                max(lst.query(0, a[i].first) - a[i].first * d,
                    rst.query(a[i].first, maxn - 1) + a[i].first * u);
        }
        long psum[m + 1];
        psum[0] = 0;
        for (int i = 0; i < m; i++) {
            psum[i + 1] = psum[i] + a[i].second;
        }
        {
            long val[m], copt = -1e18;
            for (int i = m - 1; i >= 0; i--) {
                copt = max(copt, -(u + d) * a[i].first + psum[i + 1]);
                val[i] = copt + (u + d) * a[i].first - psum[i] + mval[i];
            }
            copt = -1e18;
            for (int i = m - 1; i >= 0; i--) {
                copt = max(copt, -u * a[i].first + psum[i] + val[i]);
                opt[i] = max(opt[i], copt + u * a[i].first - psum[i]);
            }
        }
        {
            long val[m], copt = -1e18;
            for (int i = 0; i < m; i++) {
                copt = max(copt, (u + d) * a[i].first - psum[i]);
                val[i] = copt - (u + d) * a[i].first + psum[i + 1] + mval[i];
            }
            copt = -1e18;
            for (int i = 0; i < m; i++) {
                copt = max(copt, d * a[i].first - psum[i + 1] + val[i]);
                opt[i] = max(opt[i], copt - d * a[i].first + psum[i + 1]);
            }
        }
        for (int i = 0; i < m; i++) {
            lst.update(a[i].first, opt[i] + a[i].first * d);
            rst.update(a[i].first, opt[i] - a[i].first * u);
        }
    }
    cout << lst.query(s, s) - s * d << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 29012 KB Output is correct
2 Correct 16 ms 28956 KB Output is correct
3 Correct 17 ms 29012 KB Output is correct
4 Correct 17 ms 29132 KB Output is correct
5 Correct 19 ms 29204 KB Output is correct
6 Correct 39 ms 29960 KB Output is correct
7 Correct 81 ms 31484 KB Output is correct
8 Correct 145 ms 33940 KB Output is correct
9 Correct 207 ms 36172 KB Output is correct
10 Correct 341 ms 43240 KB Output is correct
11 Correct 413 ms 43884 KB Output is correct
12 Correct 552 ms 47580 KB Output is correct
13 Correct 545 ms 48040 KB Output is correct
14 Correct 664 ms 53708 KB Output is correct
15 Correct 568 ms 52720 KB Output is correct
16 Correct 679 ms 52808 KB Output is correct
17 Correct 16 ms 29012 KB Output is correct
18 Correct 16 ms 29012 KB Output is correct
19 Correct 16 ms 29048 KB Output is correct
20 Correct 17 ms 29092 KB Output is correct
21 Correct 17 ms 29064 KB Output is correct
22 Correct 19 ms 29180 KB Output is correct
23 Correct 19 ms 29140 KB Output is correct
24 Correct 19 ms 29140 KB Output is correct
25 Correct 106 ms 31500 KB Output is correct
26 Correct 188 ms 34764 KB Output is correct
27 Correct 308 ms 39056 KB Output is correct
28 Correct 344 ms 39264 KB Output is correct
29 Correct 461 ms 40684 KB Output is correct
30 Correct 439 ms 43968 KB Output is correct