제출 #1195201

#제출 시각아이디문제언어결과실행 시간메모리
1195201hafoSalesman (IOI09_salesman)C++20
62 / 100
789 ms49384 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 5e5 + 7; const ll oo = (ll) 1e9 + 69; const int lim = 5e5 + 1; int n, u, d, s, f[maxn]; pa sameDay[maxn]; vector<int> val; int dp[maxn][2]; struct market { int t, l, m; friend bool operator < (market a, market b) { if(a.t == b.t) return a.l < b.l; return a.t < b.t; } } a[maxn]; struct ST{ struct node { int mx; friend node operator + (node a, node b) { maxi(a.mx, b.mx); return a; } }; node st[4 * maxn]; void init() { for(int i = 0; i <= 4 * lim; i++) { st[i].mx = -oo; } } void update(int id, int l, int r, int pos, ll val) { if(pos < l || pos > r) return; if(l == r) { st[id].mx = val; return; } int mid = l + r >> 1; update(id << 1, l, mid, pos, val); update(id << 1 | 1, mid + 1, r, pos, val); st[id] = st[id << 1] + st[id << 1 | 1]; } node get(int id, int l, int r, int u, int v) { if(r < u || l > v) return {-oo}; if(u <= l && r <= v) return st[id]; int mid = l + r >> 1; return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v); } } st[2][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>u>>d>>s; a[0] = {0, s, 0}; val.pb(0); for(int i = 1; i <= n; i++) { cin>>a[i].t>>a[i].l>>a[i].m; val.pb(a[i].t); } sort(all(val)); val.erase(unique(all(val)), val.end()); sort(a + 1, a + 1 + n); for(int i = 0; i <= n; i++) { if(i == 0 || a[i].t != a[i - 1].t) { sameDay[a[i].t].fi = i; } if(i + 1 > n || a[i].t != a[i + 1].t) { sameDay[a[i].t].se = i; } if(i > 0) f[i] = f[i - 1] + a[i].m; } for(int i = 0; i <= n; i++) { for(int j = 0; j < 2; j++) dp[i][j] = -oo; } dp[0][1] = 0; for(int i = 0; i < 2; i++) { for(int j = 0; j < 2; j++) st[i][j].init(); } st[1][0].update(1, 1, lim, s, s * d); st[1][1].update(1, 1, lim, s, -s * u); for(int x:val){ if(x == 0) continue; for(int i = sameDay[x].fi; i <= sameDay[x].se; i++) { dp[i][0] = st[1][0].get(1, 1, lim, 1, a[i].l).mx - a[i].l * d + a[i].m; maxi(dp[i][0], st[1][1].get(1, 1, lim, a[i].l, lim).mx + a[i].l * u + a[i].m); st[0][0].update(1, 1, lim, a[i].l, dp[i][0] + a[i].l * d - f[i - 1] - a[i].m); st[0][1].update(1, 1, lim, a[i].l, dp[i][0] - a[i].l * u + f[i] - a[i].m); } for(int i = sameDay[x].fi; i <= sameDay[x].se; i++) { dp[i][1] = st[0][0].get(1, 1, lim, 1, a[i].l).mx - a[i].l * d + f[i]; maxi(dp[i][1], st[0][1].get(1, 1, lim, a[i].l, lim).mx + a[i].l * u - f[i]); st[1][0].update(1, 1, lim, a[i].l, dp[i][1] + a[i].l * d); st[1][1].update(1, 1, lim, a[i].l, dp[i][1] - a[i].l * u); } for(int i = sameDay[x].fi; i <= sameDay[x].se; i++) { st[0][0].update(1, 1, lim, a[i].l, -oo); st[0][1].update(1, 1, lim, a[i].l, -oo); } } ll ans = 0; for(int i = 1; i <= n; i++) { maxi(ans, dp[i][1] - abs(s - a[i].l) * (s < a[i].l ? u:d)); } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...