# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1043384 | Sharky | Salesman (IOI09_salesman) | C++17 | 630 ms | 61008 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 如果我不曾見過太陽,那我便可以忍受黑暗。
// 但那光照亮新的原野,將我心中的荒蕪造就。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 500005;
const int INF = 1e14;
const int M = 500001;
vector<array<int, 3>> A[N]; // capital letter :o
int n, u, d, s, dp[N], dp2[N], ans = 0;
struct SegTree {
int size = 1;
vector<array<int, 2>> seg;
void init(int _n) {
while (size < _n) size *= 2;
seg.assign(2 * size + 10, {-INF, -INF});
}
void update(int pos, int val, int l, int r, int id) {
if (l == r) {
seg[id][0] = val - pos * u;
seg[id][1] = val + pos * d;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(pos, val, l, mid, id * 2);
else update(pos, val, mid + 1, r, id * 2 + 1);
seg[id][0] = max(seg[id * 2][0], seg[id * 2 + 1][0]);
seg[id][1] = max(seg[id * 2][1], seg[id * 2 + 1][1]);
}
int query(int f, int ql, int qr, int l, int r, int id) {
if (qr < l || r < ql) return -INF;
if (ql <= l && r <= qr) return seg[id][f];
int mid = (l + r) >> 1;
return max(query(f, ql, qr, l, mid, id * 2), query(f, ql, qr, mid + 1, r, id * 2 + 1));
}
} ST;
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> u >> d >> s;
for (int i = 1, ti, loc, money; i <= n; i++) {
cin >> ti >> loc >> money;
A[ti].push_back({loc, money, i});
dp[i] = dp2[i] = -INF;
}
ST.init(M + 1);
ST.update(s, 0, 1, M, 1);
dp[0] = dp2[0] = 0;
for (int i = 0; i < N; i++) sort(A[i].begin(), A[i].end(), [] (auto a, auto b) { return a[0] < b[0]; });
for (int i = 1; i <= M; i++) {
for (auto& [loc, money, id] : A[i]) {
dp[id] = max({dp[id], ST.query(1, 1, loc - 1, 1, M, 1) - loc * d + money, ST.query(0, loc + 1, M, 1, M, 1) + loc * u + money});
ST.update(loc, dp[id], 1, M, 1);
}
for (auto& [loc, money, id] : A[i]) ST.update(loc, -INF, 1, M, 1);
reverse(A[i].begin(), A[i].end());
for (auto& [loc, money, id] : A[i]) {
dp2[id] = max({dp2[id], ST.query(0, loc + 1, M, 1, M, 1) + loc * u + money, ST.query(1, 1, loc - 1, 1, M, 1) - loc * d + money});
ST.update(loc, dp2[id], 1, M, 1);
dp[id] = max(dp[id], dp2[id]);
ans = max(ans, dp[id] - ((s > loc) ? (s - loc) * d : (loc - s) * u));
}
for (auto& [loc, money, id] : A[i]) ST.update(loc, dp[id], 1, M, 1);
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |