This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5 + 5, maxN = 2e6 + 5;
const ll INF = 1e15;
int n, u, d, s;
vector<pair<int,int>> a[maxn+1];
ll seg[maxN][2];
void build(int id, int l, int r) {
if (l==r) {
if (l==s) seg[id][0] = -(l-1) * u, seg[id][1] = -(maxn-l) * d;
else seg[id][0] = seg[id][1] = -INF;
return;
}
int mid = (l+r)/2;
build(id*2, l, mid); build(id*2+1, mid+1, r);
seg[id][0] = max(seg[id*2][0], seg[id*2+1][0]);
seg[id][1] = max(seg[id*2][1], seg[id*2+1][1]);
}
void update(int id, int l, int r, int target, int val) {
if (r<target || target<l) return;
if (l==r) {
seg[id][0] = val - (l-1) * u, seg[id][1] = val - (maxn-l) * d;
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, target, val); update(id*2+1, mid+1, r, target, val);
seg[id][0] = max(seg[id*2][0], seg[id*2+1][0]);
seg[id][1] = max(seg[id*2][1], seg[id*2+1][1]);
}
ll qry(int id, int l, int r, int findl, int findr, int j) {
if (r<findl || findr<l) return -INF;
if (findl<=l && r<=findr) return seg[id][j];
int mid = (l+r)/2;
return max(qry(id*2, l, mid, findl, findr, j), qry(id*2+1, mid+1, r, findl, findr, j));
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> u >> d >> s;
for (int i=1;i<=n;i++) {
int t, pos, val;
cin >> t >> pos >> val;
a[t].push_back({pos, val});
}
for (int i=1;i<=maxn;i++) {
a[i].push_back({0, -INF}); a[i].push_back({maxn+1, -INF});
sort(a[i].begin(), a[i].end());
}
build(1, 1, maxn);
for (int i=1;i<=maxn;i++) {
int sz = a[i].size();
if (sz==2) continue;
vector<ll> ans0(sz), ans1(sz);
for (int j=1;j<=sz-2;j++) {
ll val1 = qry(1, 1, maxn, 1, a[i][j].first, 1) + (maxn-a[i][j].first) * d;
ll val2 = qry(1, 1, maxn, a[i][j].first, maxn, 0) + (a[i][j].first-1) * u;
ans0[j] = ans1[j] = max(val1, val2);
}
ll last = -maxn * d;
for (int j=1;j<=sz-2;j++) {
last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
ans1[j] += last + (maxn-a[i][j].first) * d;
// cout << last + (maxn-a[i][j].first) * d << endl;
}
for (int j=sz-2;j>=1;j--) {
last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
ans0[j] += last + (a[i][j].first-1) * u;
}
// cout << sz << endl;
// cout << ans0[1] << " " << ans1[1] << endl;
// cout << ans0[2] << " " << ans1[2] << endl;
// cout << ans0[3] << " " << ans1[3] << endl;
// cout << endl;
ans1[0] = ans0[sz-1] = -INF;
for (int j=1;j<=sz-2;j++) ans1[j] = max(ans1[j-1] - (a[i][j].first - a[i][j-1].first) * d + a[i][j].second, ans1[j]);
for (int j=sz-2;j>=1;j--) ans0[j] = max(ans0[j+1] - (a[i][j+1].first - a[i][j].first) * u + a[i][j].second, ans0[j]);
for (int j=1;j<=sz-2;j++) update(1, 1, maxn, a[i][j].first, max(ans1[j], ans0[j]));
// cout << ans0[1] << " " << ans1[1] << endl;
// cout << ans0[2] << " " << ans1[2] << endl;
// cout << ans0[3] << " " << ans1[3] << endl;
// cout << endl;
}
ll ans = 0;
for (int i=1;i<=maxn;i++) {
ll val = qry(1, 1, maxn, i, i, 0) + (i-1) * u;
if (i<s) val -= (s-i) * d;
else val -= (i-s) * u;
ans = max(val, ans);
}
cout << ans << endl;
}
Compilation message (stderr)
salesman.cpp: In function 'int main()':
salesman.cpp:64:95: error: no matching function for call to 'max(long long int, int)'
64 | last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
salesman.cpp:64:95: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
64 | last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
salesman.cpp:64:95: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
64 | last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
salesman.cpp:64:95: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
64 | last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
salesman.cpp:64:95: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
64 | last = max(last - (a[i][j].first - a[i][j-1].first) * u, -(maxn-a[i][j].first) * d) + a[i][j].second;
| ^
salesman.cpp:69:92: error: no matching function for call to 'max(long long int, int)'
69 | last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
salesman.cpp:69:92: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
69 | last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
salesman.cpp:69:92: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
69 | last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
salesman.cpp:69:92: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
69 | last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from salesman.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
salesman.cpp:69:92: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
69 | last = max(last - (a[i][j+1].first - a[i][j].first) * d, -(a[i][j].first-1) * u) + a[i][j].second;
| ^