제출 #1043395

#제출 시각아이디문제언어결과실행 시간메모리
1043395onbertSalesman (IOI09_salesman)C++17
40 / 100
497 ms57168 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int maxn = 5e5 + 5, maxN = 2e6 + 5; const ll INF = 1e9; 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); } int 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...