# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
119781 | win11905 | Salesman (IOI09_salesman) | C++11 | 1089 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define long long long
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const long INF = 1e12;
const int N = 1<<19;
int n, u, d, s;
long t1[N<<1], t2[N<<1];
void update(long t[], int x, long v) {
x += N;
for(t[x] = max(t[x], v); x != 1; x >>= 1) t[x>>1] = max(t[x], t[x^1]);
}
long query(long t[], int l, int r) {
long mx = -INF;
for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
if(l & 1) mx = max(mx, t[l++]);
if(r & 1) mx = max(mx, t[--r]);
}
return mx;
}
long p;
void updcost(long a, long b) {
update(t1, a, b - p * a);
update(t2, a, b + p * a);
}
long getcost(long a) {
long vl = (query(t1, a, N-1) + p * a);
long vr = (query(t2, 0, a) - p * a);
return max(vl, vr);
}
int main() {
fill_n(t1, N<<1, -INF);
fill_n(t2, N<<1, -INF);
scanf("%d %d %d %d", &n, &u, &d, &s);
map<int, vector<pii>> Mp;
p = u+d;
for(int i = 0, a, b, c; i < n; ++i) {
scanf("%d %d %d", &a, &b, &c);
Mp[a].emplace_back(b, c << 1);
}
updcost(s, 0);
for(auto &x : Mp) {
vector<pii> &now = x.y;
int n = now.size();
sort(all(now));
vector<long> dp1, dp2, pref, suff, cost;
for(auto z : now) {
cost.emplace_back(getcost(z.x) + z.y);
// cerr << query(t1, z.x, N-1) << " = " << query(t2, 0, z.x) << " -> " << cost.back() << endl;
}
dp1.emplace_back(now[0].y), pref.emplace_back(now[0].y);
for(int i = 1; i < n; ++i) {
dp1.emplace_back(max(dp1.back() - 2 * p * (now[i].x - now[i-1].x), 0ll) + now[i].y);
pref.emplace_back(pref.back() + now[i].y + p * (now[i].x - now[i-1].x));
}
reverse(all(now));
dp2.emplace_back(now[0].y), suff.emplace_back(now[0].y);
for(int i = 1; i < n; ++i) {
dp2.emplace_back(max(dp2.back() - 2 * p * (now[i-1].x - now[i].x), 0ll) + now[i].y);
suff.emplace_back(suff.back() + now[i].y + p * (now[i-1].x - now[i].x));
}
reverse(all(now)), reverse(all(dp2)), reverse(all(suff));
long premax = -INF;
for(int i = 0; i < n; ++i) {
cost[i] = max(cost[i], dp2[i] - now[i].y + pref[i] + premax);
premax = max(premax, dp1[i] - pref[i] + getcost(now[i].x));
}
premax = -INF;
for(int i = n-1; i >= 0; --i) {
cost[i] = max(cost[i], dp1[i] - now[i].y + suff[i] + premax);
premax = max(premax, dp2[i] - suff[i] + getcost(now[i].x));
}
for(int i = 0; i < n; ++i) {
// cerr << x.x << " " << now[i].x << " -> " << now[i].y << " => " << cost[i] << endl;
updcost(now[i].x, cost[i]);
}
}
long ansl = query(t1, s, N-1) + p * s;
long ansr = query(t2, 0, s) - p * s;
printf("%lld\n", max(ansl, ansr) >> 1);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |