#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double Lf;
typedef pair<int, int> pii;
const int maxn = 5e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, u, d, s;
ll ans = 0;
ll f[maxn], g[maxn];
class Fair{
public:
int t, l, m;
Fair(){}
Fair(int t_, int l_, int m_): t(t_), l(l_), m(m_){}
inline bool operator < (const Fair &oth)const{ return MP(t, l) < MP(oth.t, oth.l); }
} a[maxn];
class PrefixFenwickTree{
public:
ll dat[maxn];
inline PrefixFenwickTree(){ FOR(i, 0, maxn) dat[i] = -INF; return; }
inline void update(int x, ll k){ for(++x; x < maxn; x += x & (-x)) dat[x] = max(dat[x], k); return; }
inline ll query(int x){ ll ret = -INF; for(++x; x; x -= x & (-x)) ret = max(ret, dat[x]); return ret; }
}pre;
class SuffixFenwickTree{
public:
ll dat[maxn];
inline SuffixFenwickTree(){ FOR(i, 0, maxn) dat[i] = -INF; return; }
inline void update(int x, ll k){ for(++x; x; x -= x & (-x)) dat[x] = max(dat[x], k); return; }
inline ll query(int x){ ll ret = -INF; for(++x; x < maxn; x += x & (-x)) ret = max(ret, dat[x]); return ret; }
}suf;
inline void update(int p){
pre.update(a[p].l, f[p] + a[p].l * d);
suf.update(a[p].l, f[p] - a[p].l * u);
return;
}
int main(){
scanf("%d%d%d%d", &n, &u, &d, &s);
FOR(i, 0, n)
scanf("%d%d%d", &a[i].t, &a[i].l, &a[i].m);
a[n++] = Fair(0, s, 0);
sort(a, a + n);
update(0);
for(int i = 1, j; i < n; i = j){
for(j = i; j < n && a[j].t == a[i].t; ++j)
g[j] = max(pre.query(a[j].l) - a[j].l * d, suf.query(a[j].l) + a[j].l * u), f[j] = -INF;
ll mx = -INF, sum = 0;
for(j = i; j < n && a[j].t == a[i].t; ++j){
mx = max(mx, g[j] + a[j].l * d - sum);
sum += a[j].m;
f[j] = max(f[j], mx - a[j].l * d + sum);
}
mx = -INF, sum = 0;
for(--j; j >= i; --j){
mx = max(mx, g[j] - a[j].l * u - sum);
sum += a[j].m;
f[j] = max(f[j], mx + a[j].l * u + sum);
}
for(j = i; j < n && a[j].t == a[i].t; ++j)
update(j);
}
FOR(i, 0, n)
ans = max(ans, f[i] - (a[i].l < a[0].l ? (a[0].l - a[i].l) * d : (a[i].l - a[0].l) * u));
printf("%lld\n", ans);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
56 | scanf("%d%d%d%d", &n, &u, &d, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
59 | scanf("%d%d%d", &a[i].t, &a[i].l, &a[i].m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8172 KB |
Output is correct |
2 |
Correct |
5 ms |
8172 KB |
Output is correct |
3 |
Correct |
5 ms |
8192 KB |
Output is correct |
4 |
Correct |
6 ms |
8172 KB |
Output is correct |
5 |
Correct |
7 ms |
8320 KB |
Output is correct |
6 |
Correct |
19 ms |
8812 KB |
Output is correct |
7 |
Correct |
41 ms |
9580 KB |
Output is correct |
8 |
Correct |
77 ms |
10860 KB |
Output is correct |
9 |
Correct |
110 ms |
12268 KB |
Output is correct |
10 |
Correct |
197 ms |
16364 KB |
Output is correct |
11 |
Correct |
227 ms |
16360 KB |
Output is correct |
12 |
Correct |
298 ms |
19180 KB |
Output is correct |
13 |
Correct |
288 ms |
19296 KB |
Output is correct |
14 |
Correct |
365 ms |
22028 KB |
Output is correct |
15 |
Correct |
308 ms |
21996 KB |
Output is correct |
16 |
Correct |
376 ms |
21844 KB |
Output is correct |
17 |
Correct |
4 ms |
8172 KB |
Output is correct |
18 |
Correct |
5 ms |
8172 KB |
Output is correct |
19 |
Correct |
6 ms |
8172 KB |
Output is correct |
20 |
Correct |
8 ms |
8172 KB |
Output is correct |
21 |
Correct |
6 ms |
8172 KB |
Output is correct |
22 |
Correct |
7 ms |
8300 KB |
Output is correct |
23 |
Correct |
7 ms |
8300 KB |
Output is correct |
24 |
Correct |
7 ms |
8300 KB |
Output is correct |
25 |
Correct |
70 ms |
10860 KB |
Output is correct |
26 |
Correct |
131 ms |
13612 KB |
Output is correct |
27 |
Correct |
211 ms |
17772 KB |
Output is correct |
28 |
Correct |
227 ms |
17772 KB |
Output is correct |
29 |
Correct |
340 ms |
21996 KB |
Output is correct |
30 |
Correct |
310 ms |
21868 KB |
Output is correct |