제출 #986689

#제출 시각아이디문제언어결과실행 시간메모리
986689JooDdaeSalesman (IOI09_salesman)C++17
100 / 100
357 ms42696 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("avx2") #include <bits/stdc++.h> using namespace std; using ll = long long; #define mid ((l+r) >> 1) const int INF = 2e9, N = 5e5+1; int n, u, d, s, mx[500500], t1[500500], t2[500500]; vector<array<int, 2>> v[500500]; void update(int t[], int b, int x) { while(b <= N) t[b] = max(t[b], x), b += b & -b; } int find(int t[], int b) { int re = -INF; while(b) re = max(re, t[b]), b -= b & -b; return re; } 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+N+1, -INF), fill(t2, t2+N+1, -INF); fill(mx, mx+N+1, -INF); update(t1, s, s*u), update(t2, N-s+1, -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, x-1) - x*u, x*d + find(t2, N-x)) + y; for(auto [x, y] : v[t]) { update(t1, x, x*u+mx[x]); update(t2, N-x+1, mx[x]-x*d); } for(auto [x, y] : v[t]) { auto k = find(t1, 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, N-x) + y; mx[x] = max(mx[x], k), update(t2, N-x+1, k-x*d); } for(auto [x, y] : v[t]) { update(t1, x, x*u+mx[x]); update(t2, N-x+1, mx[x]-x*d); } } int ans = 0; for(int i=1;i<=N;i++) ans = max(ans, mx[i] - abs(i-s)*(i<s ? u:d)); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...