#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
struct fair {
int t, l, m;
bool operator<(fair o) const {
if (t == o.t) {
return l < o.l;
}
return t < o.t;
}
};
vector<fair> fairs;
struct node {
int l, r, val;
node *lc, *rc;
node(int _l, int _r) : l(_l), r(_r) {
if (l == r) {
val = INT_MIN/2;
return;
}
int mid = (l + r) / 2;
lc = new node(l, mid);
rc = new node(mid + 1, r);
val = max(lc->val, rc->val);
}
void set(int loc, int nv) {
if (loc == l) {
val = nv;
return;
}
int mid = (l + r) / 2;
if (loc <= mid) {
lc->set(loc, nv);
} else rc->set(loc, nv);
val = max(lc->val, rc->val);
}
int query(int ql, int qr) {
if (ql <= l && r <= qr) return val;
if (l > qr || r < ql) return INT_MIN/2;
return max(lc->query(ql, qr), rc->query(ql, qr));
}
};
int n, u, d, s;
int cost(int a, int b) {
if (a == b) return 0;
if (a < b) {
return (b-a) * d;
} else return (a-b) * u;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("salesman.in", "r", stdin);
// freopen("salesman.out", "w", stdout);
cin >> n >> u >> d >> s;
for (int i = 0; i < n; i++) {
int t, l, m; cin >> t >> l >> m;
fairs.push_back({t, l, m});
}
sort(fairs.begin(), fairs.end());
vector<int> equal;
int ct = 1;
for (int i = 0; i < n; i++) {
if (i == n-1) {
equal.push_back(ct);
continue;
}
if (fairs[i].t != fairs[i+1].t) {
equal.push_back(ct); ct = 1;
} else {
ct++;
}
}
node *up = new node(1, 500001);
node *down = new node(1, 500001);
up->set(s, -u*s); down->set(s, d*s);
int id = 0;
for (int i = 0; i < n;) {
int ub = i + equal[id];
vector<int> curmax(equal[id]);
vector<int> lhmax(equal[id]);
vector<int> hlmax(equal[id]);
for (int j = i; j < ub; j++) {
curmax[j-i] = max(up->query(fairs[j].l, 500001) + fairs[j].l*u, down->query(1, fairs[j].l) - fairs[j].l*d) + fairs[j].m;
}
for (int j = i; j < ub; j++) {
if (i == j) lhmax[0] = curmax[0];
else {
lhmax[j-i] = curmax[j-i];
lhmax[j-i] = max(lhmax[j-i], lhmax[j-i-1] - cost(fairs[j-1].l, fairs[j].l) + fairs[j].m);
}
}
for (int j = ub-1; j >= i; j--) {
if (j == ub-1) hlmax[j-i] = curmax[j-i];
else {
hlmax[j-i] = curmax[j-i];
hlmax[j-i] = max(hlmax[j-i], hlmax[j-i+1] - cost(fairs[j+1].l, fairs[j].l) + fairs[j].m);
}
}
for (int j = i; j < ub; j++) {
curmax[j-i] = max({curmax[j-i], hlmax[j-i], lhmax[j-i]});
}
for (int j = i; j < ub; j++) {
up->set(fairs[j].l, curmax[j-i] - u*fairs[j].l);
down->set(fairs[j].l, curmax[j-i] + d * fairs[j].l);
}
i = ub; id++;
}
int ans = max(down->query(1, s) - s*d, up->query(s, 500001) + s*u);
cout << max(ans, 0) << endl;
// cout << equal;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
60 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
59 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
66 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
73 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
101 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
143 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
150 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
173 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
171 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
221 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
202 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
208 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
54 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
56 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
67 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
56 ms |
65536 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
54 ms |
65536 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
63 ms |
65536 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
58 ms |
65536 KB |
Execution killed with signal 9 |
| 24 |
Runtime error |
63 ms |
65536 KB |
Execution killed with signal 9 |
| 25 |
Runtime error |
87 ms |
65536 KB |
Execution killed with signal 9 |
| 26 |
Runtime error |
116 ms |
65536 KB |
Execution killed with signal 9 |
| 27 |
Runtime error |
164 ms |
65536 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
164 ms |
65536 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
203 ms |
65536 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
221 ms |
65536 KB |
Execution killed with signal 9 |
