oj.uz

답안 #374436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374436 2021-03-07T09:46:41 Z jhwest2 Salesman (IOI09_salesman) C++14
100 / 100
 1198 ms 17680 KB 
#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 int INF = 2.1e9;

int n, u, d, s, Dp[MAX];
pair<pint, int> A[MAX];

struct SEG {
    int T[4 * MAX];

    int 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));
    }
    int 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));
    }
    int 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<pint> 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);

        int 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);
        }
    }

    int 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

salesman.cpp: In member function 'int 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 'int 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 'int 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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 8684 KB Output is correct
2 Correct 17 ms 8556 KB Output is correct
3 Correct 18 ms 8556 KB Output is correct
4 Correct 20 ms 8556 KB Output is correct
5 Correct 27 ms 8684 KB Output is correct
6 Correct 69 ms 8940 KB Output is correct
7 Correct 134 ms 9324 KB Output is correct
8 Correct 253 ms 10092 KB Output is correct
9 Correct 400 ms 10988 KB Output is correct
10 Correct 579 ms 13420 KB Output is correct
11 Correct 756 ms 13548 KB Output is correct
12 Correct 1016 ms 14956 KB Output is correct
13 Correct 1020 ms 14804 KB Output is correct
14 Correct 1198 ms 16644 KB Output is correct
15 Correct 924 ms 16344 KB Output is correct
16 Correct 1172 ms 16620 KB Output is correct
17 Correct 18 ms 8556 KB Output is correct
18 Correct 19 ms 8556 KB Output is correct
19 Correct 20 ms 8684 KB Output is correct
20 Correct 22 ms 8684 KB Output is correct
21 Correct 25 ms 8684 KB Output is correct
22 Correct 26 ms 8684 KB Output is correct
23 Correct 27 ms 8684 KB Output is correct
24 Correct 27 ms 8684 KB Output is correct
25 Correct 256 ms 10252 KB Output is correct
26 Correct 459 ms 12332 KB Output is correct
27 Correct 738 ms 15640 KB Output is correct
28 Correct 839 ms 14772 KB Output is correct
29 Correct 1129 ms 16700 KB Output is correct
30 Correct 1083 ms 17680 KB Output is correct