#include <bits/stdc++.h>
#define int long long
#define ll long long
#define f first
#define s second
#define pii pair<int, int>
using namespace std;
const int MAXN = 500005;
int N, U, D, S;
int days[MAXN+1], dollars[MAXN+1];
ll tmp[MAXN+1];
vector<pii> vec[MAXN+1];
struct SegmentTree {
ll seg[(MAXN+2)*4];
ll lazy[(MAXN+2)*4];
SegmentTree() {
memset(seg, 0, sizeof(seg));
memset(lazy, 0, sizeof(lazy));
}
//| 1 | 2 | 3 | ==> location (index)
//| -2D | -1D | -0D | ==> segl
//| -0U | -1U | -2U | ==> segr
void prop(int val, int idx, int l, int r) {
seg[idx] += val;
if (l != r) {
lazy[idx*2] += val;
lazy[idx*2+1] += val;
}
}
void update(int ui, ll val, int idx, int l, int r) {
if (lazy[idx] != 0) {
prop(lazy[idx], idx, l, r);
lazy[idx] = 0;
}
if (ui < l || r < ui) return;
if (l == r) {
seg[idx] = max(seg[idx], val);
return;
}
int mid = (l + r) >> 1;
update(ui, val, idx*2, l, mid);
update(ui, val, idx*2+1, mid+1, r);
seg[idx] = max(seg[idx*2], seg[idx*2+1]);
}
ll gett(int gl, int gr, int idx, int l, int r) {
if (lazy[idx] != 0) {
prop(lazy[idx], idx, l, r);
lazy[idx] = 0;
}
if (gr < l || r < gl) return LLONG_MIN;
if (gl <= l && r <= gr) {
return seg[idx];
}
int mid = (l + r) >> 1;
ll resl = gett(gl, gr, idx*2, l, mid);
ll resr = gett(gl, gr, idx*2+1, mid+1, r);
return max(resl, resr);
}
void update(int ui, ll val) { update(ui, val, 1, 1, MAXN); }
ll gett(int gl, int gr) { return gett(gl, gr, 1, 1, MAXN); }
} segl, segr;
void buildAll(int idx, int l, int r) {
if (l == r) {
segl.seg[idx] = segr.seg[idx] = LLONG_MIN;
return;
}
int mid = (l + r) >> 1;
buildAll(idx*2, l, mid);
buildAll(idx*2+1, mid+1, r);
segl.seg[idx] = segr.seg[idx] = LLONG_MIN;
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> U >> D >> S;
int t, l, m; // days, location, dollars
for (int i = 1; i <= N; i++) {
cin >> t >> l >> m;
days[l] = t;
dollars[l] = m;
}
for (int l = 1; l <= MAXN; l++) {
if (days[l] != 0) vec[days[l]].push_back({ l, dollars[l] });
}
buildAll(1, 1, MAXN);
for (int t = 1; t <= MAXN; t++) {
if (vec[t].empty()) continue;
// cerr << "t: " << t << "\n";
// from day t-1 to day t
for (int i = 0; i < vec[t].size(); i++) {
auto [l, m] = vec[t][i];
// set default value
if (l < S) tmp[i] = m - (S - l) * U;
else tmp[i] = m - (l - S) * D;
ll resl = LLONG_MIN, resr = LLONG_MIN;
if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;
tmp[i] = max(tmp[i], max(resl, resr));
}
// assign new value
for (int i = 0; i < vec[t].size(); i++) {
if (tmp[i] == LLONG_MIN) continue;
auto [l, m] = vec[t][i];
// cerr << "tmp: " << l << " = " << tmp[i] << "\n";
segl.update(l, tmp[i] - (MAXN-l) * D);
segr.update(l, tmp[i] - (l-1) * U);
}
// from day t to day t (l to r)
for (int i = 0; i < vec[t].size(); i++) {
auto [l, m] = vec[t][i];
ll resl = LLONG_MIN;
if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
if (resl == LLONG_MIN || segl.gett(1, l-1) == LLONG_MIN) continue;
tmp[i] = max(tmp[i], resl);
segl.update(l, resl - (MAXN-l) * D);
}
// from day t to day t (r to l)
for (int i = (int)vec[t].size()-1; i >= 0; i--) {
auto [l, m] = vec[t][i];
ll resr = LLONG_MIN;
if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;
if (resr == LLONG_MIN || segr.gett(l+1, MAXN) == LLONG_MIN) continue;
tmp[i] = max(tmp[i], resr);
segr.update(l, resr - (l-1) * U);
}
// assign new value
for (int i = 0; i < vec[t].size(); i++) {
if (tmp[i] == LLONG_MIN) continue;
auto [l, m] = vec[t][i];
segl.update(l, tmp[i] - (MAXN-l) * D);
segr.update(l, tmp[i] - (l-1) * U);
// cerr << l << " is " << segl.gett(l, l) + (MAXN-l) * D << "\n";
}
continue;
continue;
continue;
continue;
// (again) from day t to day t (l to r)
for (int i = 0; i < vec[t].size(); i++) {
auto [l, m] = vec[t][i];
ll resr = LLONG_MIN;
if (l+1 <= MAXN) resr = segr.gett(l+1, MAXN) + (l-1) * U + m;
if (resr == LLONG_MIN || segr.gett(l+1, MAXN) == LLONG_MIN) continue;
tmp[i] = max(tmp[i], resr);
segr.update(l, resr - (l-1) * U);
}
// (again) from day t to day t (r to l)
for (int i = vec[t].size()-1; i >= 0; i--) {
auto [l, m] = vec[t][i];
ll resl = LLONG_MIN;
if (1 <= l-1) resl = segl.gett(1, l-1) + (MAXN-l) * D + m;
if (resl == LLONG_MIN || segl.gett(1, l-1) == LLONG_MIN) continue;
tmp[i] = max(tmp[i], resl);
segl.update(l, resl - (MAXN-l) * D);
}
// (again) assign new value
for (int i = 0; i < vec[t].size(); i++) {
if (tmp[i] == LLONG_MIN) continue;
auto [l, m] = vec[t][i];
segl.update(l, tmp[i] - (MAXN-l) * D);
segr.update(l, tmp[i] - (l-1) * U);
// cerr << "(again) " << l << " is " << segl.gett(l, l) + (MAXN-l) * D << "\n";
}
}
ll resl = LLONG_MIN, resr = LLONG_MIN;
if (1 <= S-1) resl = segl.gett(1, S-1) + (MAXN-S) * D;
if (S+1 <= MAXN) resr = segr.gett(S+1, MAXN) + (S-1) * U;
cout << max({ 0LL, resl, resr }) << "\n";
return 0;
}
Compilation message
salesman.cpp: In function 'int32_t main()':
salesman.cpp:122:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < vec[t].size(); i++) {
| ~~^~~~~~~~~~~~~~~
salesman.cpp:123:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
123 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:137:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 0; i < vec[t].size(); i++) {
| ~~^~~~~~~~~~~~~~~
salesman.cpp:140:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
140 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:147:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int i = 0; i < vec[t].size(); i++) {
| ~~^~~~~~~~~~~~~~~
salesman.cpp:148:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
148 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:160:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
160 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:171:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
171 | for (int i = 0; i < vec[t].size(); i++) {
| ~~^~~~~~~~~~~~~~~
salesman.cpp:174:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
174 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:187:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for (int i = 0; i < vec[t].size(); i++) {
| ~~^~~~~~~~~~~~~~~
salesman.cpp:188:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
188 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:200:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
200 | auto [l, m] = vec[t][i];
| ^
salesman.cpp:211:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for (int i = 0; i < vec[t].size(); i++) {
| ~~^~~~~~~~~~~~~~~
salesman.cpp:214:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
214 | auto [l, m] = vec[t][i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
11 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
11 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
11 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
13 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
13 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
15 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
27 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
13 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
10 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
24 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
13 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
10 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
14 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
10 ms |
65536 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 24 |
Runtime error |
10 ms |
65536 KB |
Execution killed with signal 9 |
| 25 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 26 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 27 |
Runtime error |
28 ms |
65536 KB |
Execution killed with signal 9 |
| 28 |
Runtime error |
12 ms |
65536 KB |
Execution killed with signal 9 |
| 29 |
Runtime error |
13 ms |
65536 KB |
Execution killed with signal 9 |
| 30 |
Runtime error |
27 ms |
65536 KB |
Execution killed with signal 9 |
