/**
00 00 11 00 00 111111 00000 111111 000000
00 00 1111 0000 11 00 11 11 000000
0000 11 11 00 11 00000 111111 00
00 00 11111111 0000 11 00 11 11 00
00 00 11 11 00 00 111111 00000 11 11 00
**/
#include<bits/stdc++.h>
using namespace std;
void setIO(string s) {
freopen((s+".inp").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
void setIOusaco(string s) {
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define fast ios::sync_with_stdio(false); cin.tie(0)
void print(int x) {cout << x;}
void print(long long x) {cout << x;}
void print(unsigned x) {cout << x;}
void print(unsigned long long x) {cout << x;}
void print(double x) {cout << fixed << x;}
void print(long double x) {cout << fixed << x;}
void print(char x) {cout << "'" << x << "'";}
void print(string x) {cout << '"' << x << '"';}
void print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void print(const pair<T, V> &x) {cout << '{'; print(x.ff); cout << ", "; print(x.ss); cout << '}';}
template<typename T>
void print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? ", " : ""), print(i); cout << "}";}
void _print() {cout << "]" << endl;}
template <typename T, typename... V>
void _print(T t, V... v) {print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifdef TAP
#define bug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define bug(x...)
#endif
template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}
#define maxN 500008
const ll oo = (ll)1e16;
ll f[maxN];
int n, u, d, s;
struct segment_tree {
vt<ll> nodes;
segment_tree() {
nodes.assign(n*4, -oo);
}
void update(int i, ll val, int root = 1, int left = 1, int right = n) {
if (left == right && left == i) {
nodes[root] = max(nodes[root], val);
return;
}
if (left > i || right < i) return;
int mid = (left+right)/2;
update(i, val, root*2, left, mid);
update(i, val, root*2+1, mid+1, right);
nodes[root] = max(nodes[root*2], nodes[root*2+1]);
}
ll getquery(int i, int j, int root = 1, int left = 1, int right = n) {
if (left >= i && right <= j) return nodes[root];
if (left > j || right < i) return -oo;
int mid = (left+right)/2;
return max(getquery(i, j, root*2, left, mid), getquery(i, j, root*2+1, mid+1, right));
}
};
int main() {
fast;
cin >> n >> u >> d >> s;
vt<array<int, 3> > a;
vt<int> b;
b.pb(s);
fto(i, 1, n) {
int day, loc, cost;
cin >> day >> loc >> cost;
a.pb({day, loc, cost});
b.pb(loc);
}
a.pb({600000, s, 0});
sort(all(a), [](array<int, 3> a, array<int, 3> b) -> bool {
if (a[0] < b[0]) return 1;
if (a[0] > b[0]) return 0;
return a[1] < b[1];
});
sort(all(b));
b.erase(unique(all(b)), b.end());
n = sz(b);
segment_tree up, down;
auto tk = [=](int loc) -> int{
return ((lower_bound(all(b), loc))-b.begin()) + 1;
};
int sth = tk(s);
up.update(sth, -u*s);
down.update(sth, d*s);
// fto(i, 0, sz(a)-1) {
// bug(a[i]);
// }
int left = 0, right = 0;
ll ans;
fto(i, 0, sz(a)-1) {
if (i < sz(a)-1 && a[i][0] == a[i+1][0]) {
++right;
continue;
}
else {
//bug(left, right);
vt<ll> temp1(right-left+1);
priority_queue<ll> q1;
fto(j, left, right) {
int loc = tk(a[j][1]);
temp1[j-left] = max(down.getquery(1, loc) -a[j][1]*d + a[j][2], up.getquery(loc, n) + a[j][1]*u + a[j][2]);
if (!q1.empty()) temp1[j-left] = max(temp1[j-left], q1.top() -a[j][1]*d + a[j][2]);
q1.push(temp1[j-left] + d*a[j][1]);
}
//bug(temp1);
vt<ll> temp2(right-left+1);
priority_queue<ll> q2;
fdto(j, right, left) {
int loc = tk(a[j][1]);
temp2[j-left] = max(down.getquery(1, loc) -a[j][1]*d + a[j][2], up.getquery(loc, n) + a[j][1]*u + a[j][2]);
if (!q2.empty()) temp2[j-left] = max(temp2[j-left], q2.top() + a[j][1]*u + a[j][2]);
q2.push(temp2[j-left] - u*a[j][1]);
}
//bug(temp2);
fto(j, left, right) {
if (j == sz(a)-1) ans = max(temp1[j-left], temp2[j-left]);
int loc = tk(a[j][1]);
up.update(loc, max(temp1[j-left], temp2[j-left]) - u*a[j][1]);
down.update(loc, max(temp1[j-left], temp2[j-left]) + d*a[j][1]);
}
left = i+1;
right = i+1;
}
}
cout << ans << '\n';
return 0;
}
Compilation message
salesman.cpp: In function 'void setIO(std::string)':
salesman.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen((s+".inp").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp: In function 'void setIOusaco(std::string)':
salesman.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
4 ms |
460 KB |
Output is correct |
| 5 |
Correct |
9 ms |
844 KB |
Output is correct |
| 6 |
Correct |
43 ms |
2404 KB |
Output is correct |
| 7 |
Correct |
106 ms |
5152 KB |
Output is correct |
| 8 |
Correct |
240 ms |
9192 KB |
Output is correct |
| 9 |
Correct |
363 ms |
13308 KB |
Output is correct |
| 10 |
Correct |
645 ms |
26276 KB |
Output is correct |
| 11 |
Correct |
879 ms |
26268 KB |
Output is correct |
| 12 |
Correct |
1168 ms |
34484 KB |
Output is correct |
| 13 |
Correct |
1174 ms |
34488 KB |
Output is correct |
| 14 |
Correct |
1436 ms |
42704 KB |
Output is correct |
| 15 |
Correct |
1179 ms |
42724 KB |
Output is correct |
| 16 |
Correct |
1441 ms |
42708 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
2 ms |
332 KB |
Output is correct |
| 20 |
Correct |
4 ms |
588 KB |
Output is correct |
| 21 |
Correct |
4 ms |
588 KB |
Output is correct |
| 22 |
Correct |
9 ms |
848 KB |
Output is correct |
| 23 |
Correct |
8 ms |
904 KB |
Output is correct |
| 24 |
Correct |
9 ms |
844 KB |
Output is correct |
| 25 |
Correct |
192 ms |
9444 KB |
Output is correct |
| 26 |
Correct |
402 ms |
18664 KB |
Output is correct |
| 27 |
Correct |
738 ms |
33812 KB |
Output is correct |
| 28 |
Correct |
878 ms |
32192 KB |
Output is correct |
| 29 |
Correct |
1161 ms |
43020 KB |
Output is correct |
| 30 |
Correct |
1171 ms |
46424 KB |
Output is correct |
