제출 #991338

#제출 시각아이디문제언어결과실행 시간메모리
991338GhettoSalesman (IOI09_salesman)C++17
40 / 100
603 ms65536 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 5e5 + 5, MAX_POS = 5e5 + 5, INF = 2e9 + 5; int n, l, r, s; int day[MAX_N], pos[MAX_N], val[MAX_N]; map<int, vector<int>> days; int st[2][4 * MAX_POS]; void build(int ind) { for (int i = 1; i <= 4 * MAX_POS - 5; i++) st[ind][i] = -INF; } void update(int ind, int i, int x, int u = 1, int lo = 1, int hi = MAX_POS) { if (i < lo || hi < i) return; if (lo == hi) { st[ind][u] = x; return; } int mid = (lo + hi) / 2; update(ind, i, x, 2 * u, lo, mid), update(ind, i, x, 2 * u + 1, mid + 1, hi); st[ind][u] = max(st[ind][2 * u], st[ind][2 * u + 1]); } int query(int ind, int l, int r, int u = 1, int lo = 1, int hi = MAX_POS) { if (r < lo || hi < l) return -INF; if (l <= lo && hi <= r) return st[ind][u]; int mid = (lo + hi) / 2; return max(query(ind, l, r, 2 * u, lo, mid), query(ind, l, r, 2 * u + 1, mid + 1, hi)); } int dp[MAX_N]; void init() { build(0), build(1); day[0] = 0, pos[0] = s, val[0] = 0, dp[0] = 0; update(0, pos[0], pos[0] * r), update(1, pos[0], -pos[0] * l); day[n + 1] = INF, pos[n + 1] = s, val[n + 1] = 0, days[INF].push_back(n + 1); } int main() { // freopen("salesman.in", "r", stdin), freopen("salesman.out", "w", stdout); cin >> n >> l >> r >> s; init(); for (int i = 1; i <= n; i++) cin >> day[i] >> pos[i] >> val[i], days[day[i]].push_back(i); for (pair<int, vector<int>> x : days) { auto comp = [] (int i, int j)->bool { return pos[i] < pos[j]; }; sort(x.second.begin(), x.second.end(), comp); // cout << "NEW --------------" << x.first << endl; for (int i = 0; i <= (int) x.second.size() - 1; i++) { int ind = x.second[i]; int l_trans = query(0, 1, pos[ind]) - pos[ind] * r; int r_trans = query(1, pos[ind] + 1, MAX_POS) + pos[ind] * l; int step_trans = (i == 0) ? -INF : dp[x.second[i - 1]] + r * (pos[ind] - pos[x.second[i - 1]]); // cout << ind << ": " << l_trans << " " << r_trans << " " << step_trans << endl; dp[ind] = max({l_trans, r_trans, step_trans}) + val[ind]; } for (int ind : x.second) update(0, pos[ind], dp[ind] + pos[ind] * r), update(1, pos[ind], dp[ind] - pos[ind] * l); } cout << dp[n + 1] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...