제출 #374433

#제출 시각아이디문제언어결과실행 시간메모리
374433jhwest2Salesman (IOI09_salesman)C++14
100 / 100
1524 ms35272 KiB
#include <bits/stdc++.h> #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; }

컴파일 시 표준 에러 (stderr) 메시지

salesman.cpp: In member function 'lint SEG::init(int, int, int)':
salesman.cpp:19:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                      ~~~^~~~
salesman.cpp:19:75: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         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:24:49: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         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:24:91: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         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:29:39: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1));
      |                                    ~~~^~~~
salesman.cpp:29:80: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         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:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i = 0; i < V.size(); i++) {
      |                         ~~^~~~~~~~~~
salesman.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if (i != V.size() - 1) mx = max(mx, T.query(A[x].va.vb, A[x + 1].va.vb - 1)) + A[x].vb;
      |                 ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...