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