#include <bits/stdc++.h>
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1000000000LL;
const int MAX_N = 500001;
int N;
ll U, D, S;
struct ST{
ll t, l, m;
bool operator <(const ST &a)const{
if(t==a.t){
return l<a.l;
}
return t<a.t;
}
};
vector<ST> v;
struct SEG{
struct NODE{
int l, r;
ll mx;
};
vector<NODE> seg;
int SZ;
void add(){seg.pb({-1, -1, -INFLL});}
void Init(int x){
add();
SZ = x;
}
void Update(int x, int y, ll z){
update(0, 1, SZ, x, y, z);
}
void update(int idx, int s, int e, int x, int y, ll z){
if(x<=s && e<=y) {
seg[idx].mx = max(seg[idx].mx, z);
return;
}
if(x>e || y<s) return;
if(seg[idx].l==-1){
seg[idx].l = seg.size(); add();
}
if(seg[idx].r == -1){
seg[idx].r = seg.size(); add();
}
update(seg[idx].l, s, (s+e)/2, x, y, z); update(seg[idx].r, (s+e)/2+1, e, x, y, z);
}
ll Mx(int x){
return mx(0, 1, SZ, x);
}
ll mx(int idx, int s, int e, int k){
if(idx==-1) return -INFLL;
if(s==e) return seg[idx].mx;
if(k<=(s+e)/2){
return max(seg[idx].mx, mx(seg[idx].l, s, (s+e)/2, k));
}else{
return max(seg[idx].mx, mx(seg[idx].r, (s+e)/2+1, e, k));
}
}
}Seg1, Seg2;
vector<pair<ll, int> > vt;
ll get(ll idx){
return max(Seg1.Mx((int)idx)+idx*U, Seg2.Mx((int)idx)-idx*D);
}
void Upd(ll idx, ll x){
Seg1.Update(1, (int)idx, x-idx*U);
Seg2.Update((int)idx, MAX_N, x+idx*D);
}
ll prv[MAX_N+1];
int main(){
scanf("%d%lld%lld%lld", &N, &U, &D, &S);
Seg1.Init(MAX_N); Seg2.Init(MAX_N);
Upd(S, 0);
for(int i=0; i<N; i++){
ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
v.pb({a, b, c});
}
sort(v.begin(), v.end());
int s = 0, e = 0;
while(s<v.size()){
while(e+1<v.size() && v[e+1].t==v[s].t) e++;
if(s==e){
Upd(v[s].l, get(v[s].l)+v[s].m);
}else{
for(int i=s; i<=e; i++) prv[i] = get(v[i].l);
for(int i=s; i<=e; i++){
Seg2.Update((int)v[i].l, MAX_N, max(prv[i]+v[i].l*D, Seg2.Mx((int)v[i].l))+v[i].m);
}
for(int i=e; i>=s; i--){
Seg1.Update(1, (int)v[i].l, max(prv[i]-v[i].l*U, Seg1.Mx((int)v[i].l))+v[i].m);
}
for(int i=s; i<=e; i++){
Upd(v[i].l, get(v[i].l));
}
}
s = e+1; e++;
}
cout<<get(S);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:104:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(s<v.size()){
~^~~~~~~~~
salesman.cpp:105:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(e+1<v.size() && v[e+1].t==v[s].t) e++;
~~~^~~~~~~~~
salesman.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%lld%lld%lld", &N, &U, &D, &S);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:99:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
ll a, b, c; scanf("%lld%lld%lld", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
504 KB |
Output is correct |
4 |
Correct |
4 ms |
760 KB |
Output is correct |
5 |
Correct |
9 ms |
1112 KB |
Output is correct |
6 |
Correct |
43 ms |
7560 KB |
Output is correct |
7 |
Correct |
113 ms |
14948 KB |
Output is correct |
8 |
Correct |
221 ms |
17600 KB |
Output is correct |
9 |
Correct |
321 ms |
17904 KB |
Output is correct |
10 |
Correct |
556 ms |
45592 KB |
Output is correct |
11 |
Correct |
717 ms |
45448 KB |
Output is correct |
12 |
Execution timed out |
1016 ms |
38952 KB |
Time limit exceeded |
13 |
Execution timed out |
1010 ms |
49056 KB |
Time limit exceeded |
14 |
Execution timed out |
1082 ms |
42304 KB |
Time limit exceeded |
15 |
Correct |
981 ms |
58476 KB |
Output is correct |
16 |
Execution timed out |
1069 ms |
41088 KB |
Time limit exceeded |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
632 KB |
Output is correct |
20 |
Correct |
8 ms |
760 KB |
Output is correct |
21 |
Correct |
7 ms |
760 KB |
Output is correct |
22 |
Correct |
13 ms |
1000 KB |
Output is correct |
23 |
Correct |
14 ms |
1080 KB |
Output is correct |
24 |
Correct |
13 ms |
1080 KB |
Output is correct |
25 |
Correct |
358 ms |
21660 KB |
Output is correct |
26 |
Correct |
709 ms |
38956 KB |
Output is correct |
27 |
Execution timed out |
1064 ms |
51136 KB |
Time limit exceeded |
28 |
Execution timed out |
1081 ms |
48284 KB |
Time limit exceeded |
29 |
Execution timed out |
1066 ms |
50604 KB |
Time limit exceeded |
30 |
Execution timed out |
1079 ms |
51840 KB |
Time limit exceeded |