#include "bits/stdc++.h"
#define ll long long
#define all(x) x.begin(), x.end()
#define read(x) for(auto &i : x) cin >> i;
#define sz(x) (int) (x).size()
#define len(x) (int) (x).length()
#define arr array
constexpr int INF = 1e9 + 9;
constexpr long long INF_LL = 1e18 + 9;
constexpr int MOD = 1e9 + 7; // 998244353;
// up, right, down, left
constexpr int mX_4 [] = {0, 1, 0, -1};
constexpr int mY_4 [] = {-1, 0, 1, 0};
using namespace std;
ll rand_num(ll l, ll r) {
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
return uniform_int_distribution<ll>(l, r)(gen);
}
template <typename T>
std::ostream& operator<<(std::ostream& _os, const std::pair<T, T>& _p) {
_os << _p.first << ' ' << _p.second;
return _os;
}
template <typename T>
void dbg_vec(string str, vector <T> &x) {
cerr << "DBG " << str << '\n';
for (int i = 0; i < sz(x); ++i) {
cerr << "I " << i << " -> " << x[i] << '\n';
}
cerr << '\n';
}
const int MAX_BIT_DBG = 3;
void dbg_bits(int n) {
bitset <MAX_BIT_DBG> v (n);
cerr << v << '\n';
}
template <typename T>
bool vmin(T &a, T b) { return (a > b ? a = b, true : false); }
template <typename T>
bool vmax(T &a, T b) { return (a < b ? a = b, true : false); }
/**
* (i - j) * c --> dove c è U oppure D
* Devo trovare velocemente j che mi massimizza la cosa
* sottraggo ad value[i] i
* Per ogni valore che vado a computare, sottraggo la posizione di i --> v[j] + j + g - i se i > j
* Se i < j allora v[j] - j + g + i
* Posso tenermi 3 segment
*/
struct Segment {
vector <ll> st;
int n;
Segment(int _n) {
n = _n;
st.resize(n<<1, -INF_LL);
}
ll get(int idx) { return st[idx + n]; }
// ritorna true se l'update e' servito
bool upd(int idx, ll updV) {
idx += n;
if (vmax(st[idx], updV)) {
for (; idx > 1; idx >>= 1) {
st[idx >> 1] = max(st[idx], st[idx ^ 1]);
}
return true;
}
return false;
}
ll get_max(int l, int r) {
ll mx = -INF_LL;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) vmax(mx, st[l++]);
if (r & 1) vmax(mx, st[--r]);
}
return mx;
}
};
constexpr int MAXN = 500001;
void solve() {
int n, u, d, s; cin >> n >> u >> d >> s;
vector <map <int, int> > event (MAXN);
for (int i = 0; i < n; ++i) {
int day, pos, reward; cin >> day >> pos >> reward;
event[day][pos] += reward;
}
Segment st(MAXN);
Segment st_r(MAXN); // utilizzato se la posizione in cui sono e' < di quelli in cui voglio vedere
Segment st_l(MAXN); // utilizzato se la posizione in cui sono e' > di quelli in cui voglio vedere
// per up, devo sottrarre la posizione
// per down, devo aggiungere la posizione
st.upd(s, 0);
st_l.upd(s, -s * u);
st_r.upd(s, s * d);
for (int day = 1; day < MAXN; ++day) {
if (sz(event[day]) == 0) continue;
for (auto [pos, reward] : event[day]) {
// provo a salire per arrivare a pos --> scelgo i punti < pos dal segment up
ll mx_L = st_l.get_max(pos, MAXN);
ll mx_R = st_r.get_max(0, pos + 1);
// 3 * 20 --> -60 + 110 = 50
ll cost1 = mx_R + reward - (pos * d); // salgo a destra
ll cost2 = mx_L + reward + (pos * u); // salgo in sinistra
// cerr << "Mx_L " << mx_L << " reward " << reward << " pls " << (pos * u) << endl;
ll new_sub = max(cost1, cost2);
// cerr << "Mx_L " << mx_L << " Mx_R " << mx_R << " cost1 " << cost1 << " cost2 " << cost2 << " --> " << new_sub << endl;
if (st.upd(pos, new_sub)) { // l'update ha migliorato i costi
st_r.upd(pos, new_sub + pos * d);
st_l.upd(pos, new_sub - pos * u);
}
// cerr << "Max profitto day: " << day << " --> " << st.get_max(0, MAXN) << '\n';
// if (day == return;
}
}
// calcolo la risposta per tornare a casa -->
ll ans = 0;
for (int i = 0; i < MAXN; ++i) {
if (i == 75) {
// cerr << "Giorno " << i << " --> " << st.get(i) << '\n';
}
if (i == s) {
vmax(ans, st.get(i));
} else if (i < s) {
vmax(ans, st.get(i) - d * (s - i));
} else {
vmax(ans, st.get(i) - u * (i - s));
}
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
int tt = 1; // cin >> tt;
while (tt--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
47300 KB |
Output is correct |
| 2 |
Correct |
30 ms |
47240 KB |
Output is correct |
| 3 |
Correct |
28 ms |
47244 KB |
Output is correct |
| 4 |
Correct |
27 ms |
47336 KB |
Output is correct |
| 5 |
Correct |
32 ms |
47528 KB |
Output is correct |
| 6 |
Correct |
47 ms |
48520 KB |
Output is correct |
| 7 |
Correct |
93 ms |
50536 KB |
Output is correct |
| 8 |
Correct |
148 ms |
53776 KB |
Output is correct |
| 9 |
Correct |
196 ms |
56652 KB |
Output is correct |
| 10 |
Correct |
338 ms |
65536 KB |
Output is correct |
| 11 |
Correct |
397 ms |
65536 KB |
Output is correct |
| 12 |
Runtime error |
166 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
169 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
214 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
242 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
200 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Correct |
25 ms |
47300 KB |
Output is correct |
| 18 |
Incorrect |
24 ms |
47292 KB |
Output isn't correct |
| 19 |
Incorrect |
25 ms |
47328 KB |
Output isn't correct |
| 20 |
Incorrect |
25 ms |
47444 KB |
Output isn't correct |
| 21 |
Incorrect |
26 ms |
47340 KB |
Output isn't correct |
| 22 |
Incorrect |
28 ms |
47584 KB |
Output isn't correct |
| 23 |
Incorrect |
28 ms |
47516 KB |
Output isn't correct |
| 24 |
Incorrect |
26 ms |
47572 KB |
Output isn't correct |
| 25 |
Incorrect |
154 ms |
53388 KB |
Output isn't correct |
| 26 |
Incorrect |
304 ms |
59380 KB |
Output isn't correct |
| 27 |
Incorrect |
518 ms |
65536 KB |
Output isn't correct |
| 28 |
Incorrect |
547 ms |
65536 KB |
Output isn't correct |
| 29 |
Runtime error |
375 ms |
65536 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
411 ms |
65536 KB |
Execution killed with signal 9 |
