제출 #986682

#제출 시각아이디문제언어결과실행 시간메모리
986682JooDdaeSalesman (IOI09_salesman)C++17
40 / 100
459 ms48268 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define mid ((l+r) >> 1) const int INF = 2e9, N = 2e5+1; int n, u, d, s, mx[500500], t1[2002002], t2[2002002]; vector<array<int, 2>> v[500500]; void update(int t[], int id, int x, int node = 1, int l = 1, int r = N) { if(id < l || r < id) return; if(l == r) { t[node] = max(t[node], x); return; } update(t, id, x, node*2, l, mid), update(t, id, x, node*2+1, mid+1, r); t[node] = max(t[node*2], t[node*2+1]); } int find(int t[], int nl, int nr, int node = 1, int l = 1, int r = N) { if(nr < l || r < nl) return -INF; if(nl <= l && r <= nr) return t[node]; return max(find(t, nl, nr, node*2, l, mid), find(t, nl, nr, node*2+1, mid+1, r)); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> u >> d >> s; for(int i=1;i<=n;i++) { int t, x, y; cin >> t >> x >> y; v[t].push_back({x, y}); } fill(t1, t1+4*N+1, -INF), fill(t2, t2+4*N+1, -INF); fill(mx, mx+N+1, -INF); update(t1, s, s*u), update(t2, s, -s*d); for(int t=1;t<=N;t++) if(!v[t].empty()) { sort(v[t].begin(), v[t].end()); for(auto [x, y] : v[t]) mx[x] = max(find(t1, 1, x-1) - x*u, x*d + find(t2, x+1, N)) + y; for(auto [x, y] : v[t]) { update(t1, x, x*u+mx[x]); update(t2, x, mx[x]-x*d); } for(auto [x, y] : v[t]) { auto k = find(t1, 1, x-1) - x*u + y; mx[x] = max(mx[x], k), update(t1, x, x*u+k); } reverse(v[t].begin(), v[t].end()); for(auto [x, y] : v[t]) { auto k = x*d + find(t2, x+1, N) + y; mx[x] = max(mx[x], k), update(t2, x, k-x*d); } for(auto [x, y] : v[t]) { update(t1, x, x*u+mx[x]); update(t2, x, mx[x]-x*d); } } int ans = 0; for(int i=1;i<=N;i++) { ans = max(ans, find(t1, 1, s-1) - s*u); ans = max(ans, s*d + find(t2, s+1, N)); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...