# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
374432 | jhwest2 | Salesman (IOI09_salesman) | C++14 | 1268 ms | 35264 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |