#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ed << "\n";
#define el cout<<'\n';
#define ALL(s) s.begin(),s.end()
#define fi first
#define se second
#define SQ(a) (a)*(a)
#define A(a) abs(a)
#define SZ(a) ((int)(a.size()))
#define REP(i,a,b) for (int i = (a), _b = (b); i < _b; i++)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FOD(i,r,l) for(int i=r; i>=l; i--)
#define MASK(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define pii pair<int,int>
#define db double
#define II(a, b) make_pair((a),(b))
#define pb(x) push_back(x)
#define int ll
const int mod = 1e9 + 7;
const ll MOD = 1e12 + 7;
const ll INF = 1e18;
/// 998244353;
/// 1e9 + 7;
/// 1e9 + 25;
/// 999999939;
/// 1e12 + 7;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r) {
return l + rd() % (r - l + 1);
}
int mul(ll a, ll b) {
if(a >= mod) a %= mod;
if(b >= mod) b %= mod;
return 1LL * a * b % mod;
}
int add(int a, int b) {
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return a;
}
int pw(int a, int b) {
int res = 1;
while(b) {
if(b & 1)
res = mul(res, a);
b = b >> 1;
a = mul(a, a);
}
return res;
}
template <class T> inline bool minimize(T &a, const T &b) {
return (a > b ? (a = b),1 : 0);
}
template <class T> inline bool maximize(T &a, const T &b) {
return (a < b ? (a = b),1 : 0);
}
void ReadInp() {
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task "a"
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task "LONG"
if(fopen(task".in","r")) {
freopen(task".in","r",stdin);
freopen(task".out","w",stdout);
}
}
const int maxn = 5e5 + 5;
int n, U, D, S;
int T[maxn];
int L[maxn];
int K[maxn];
int p[maxn];
int f[maxn];
int s[maxn];
vector <pii> event[maxn];
struct BIT{
vector <int> st; int n;
void init(const int sz = 0){
n = sz; st = vector <int> (4 * n + 2, - INF);
}
void upd(int i, int val){
int l = 1, r = n, id = 1;
while(l <= r){
maximize(st[id], val);
int m = (l + r) / 2;
if(l == r) return;
if(i > m){
l = m + 1;
id = id * 2 + 1;
}else{
r = m;
id = id * 2;
}
}
}
int get(int u, int v, int l, int r, int id) const{
if(u <= l && r <= v) return st[id];
if(u > r || v < l) return - INF;
int m = (l + r) / 2;
return max(get(u, v, l, m, id * 2), get(u, v, m + 1, r, id * 2 + 1));
}
int get(int u, int v) const{
return get(u, v, 1, n, 1);
}
}it_D, it_U;
void sol() {
cin >> n >> U >> D >> S;
it_D.init(500000); it_U.init(500000);
memset(f, -0x3f, sizeof f);
memset(p, -0x3f, sizeof p);
memset(s, -0x3f, sizeof s);
swap(U, D);
f[S] = 0; it_D.upd(S, U * S); it_U.upd(S, - D * S);
FOR(i, 1, n){
int t; cin >> t;
int l, m; cin >> l >> m;
event[t].push_back(II(l, m));
}
FOR(i, 1, 500000){
sort(ALL(event[i]));
vector <int> st;
for(auto [Loc, earn] : event[i]){
maximize(p[Loc], it_D.get(1, Loc) - U * Loc + earn);
maximize(p[Loc], it_U.get(Loc, 500000) + D * Loc + earn);
s[Loc] = p[Loc];
}
for(auto [Loc, earn] : event[i]){
maximize(p[Loc], it_D.get(1, Loc) - U * Loc + earn);
it_D.upd(Loc, p[Loc] + U * Loc);
}
reverse(ALL(event[i]));
for(auto [Loc, earn] : event[i]){
maximize(s[Loc], it_U.get(Loc, 500000) + D * Loc + earn);
it_U.upd(Loc, s[Loc] - D * Loc);
}
for(auto [Loc, earn] : event[i]){
maximize(f[Loc], max(p[Loc], s[Loc]));
it_U.upd(Loc, f[Loc] - D * Loc);
it_D.upd(Loc, f[Loc] + U * Loc);
}
}
int ans = 0;
FOR(i, 1, 50000) ans = max(ans, f[i] - (S <= i ? (i - S) * D : (S - i) * U));
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
ReadInp();
int t = 1; /// cin >> t;
while(t --) sol();
return 0;
}
Compilation message
salesman.cpp:85: warning: "task" redefined
85 | #define task "LONG"
|
salesman.cpp:79: note: this is the location of the previous definition
79 | #define task "a"
|
salesman.cpp: In function 'void ReadInp()':
salesman.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
76 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(task".in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
salesman.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
55124 KB |
Output is correct |
| 2 |
Correct |
23 ms |
55112 KB |
Output is correct |
| 3 |
Correct |
24 ms |
55048 KB |
Output is correct |
| 4 |
Correct |
28 ms |
55176 KB |
Output is correct |
| 5 |
Correct |
38 ms |
55192 KB |
Output is correct |
| 6 |
Incorrect |
65 ms |
55648 KB |
Output isn't correct |
| 7 |
Correct |
130 ms |
56688 KB |
Output is correct |
| 8 |
Incorrect |
235 ms |
58308 KB |
Output isn't correct |
| 9 |
Incorrect |
353 ms |
59824 KB |
Output isn't correct |
| 10 |
Correct |
557 ms |
64524 KB |
Output is correct |
| 11 |
Incorrect |
669 ms |
64968 KB |
Output isn't correct |
| 12 |
Runtime error |
127 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
139 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
133 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Correct |
30 ms |
55124 KB |
Output is correct |
| 18 |
Correct |
25 ms |
55124 KB |
Output is correct |
| 19 |
Correct |
25 ms |
55176 KB |
Output is correct |
| 20 |
Correct |
27 ms |
55208 KB |
Output is correct |
| 21 |
Correct |
27 ms |
55120 KB |
Output is correct |
| 22 |
Correct |
31 ms |
55252 KB |
Output is correct |
| 23 |
Correct |
32 ms |
55272 KB |
Output is correct |
| 24 |
Correct |
29 ms |
55256 KB |
Output is correct |
| 25 |
Correct |
196 ms |
57172 KB |
Output is correct |
| 26 |
Correct |
317 ms |
59192 KB |
Output is correct |
| 27 |
Correct |
497 ms |
62856 KB |
Output is correct |
| 28 |
Incorrect |
586 ms |
62644 KB |
Output isn't correct |
| 29 |
Incorrect |
867 ms |
65536 KB |
Output isn't correct |
| 30 |
Incorrect |
726 ms |
65536 KB |
Output isn't correct |
