Submission #210144

#TimeUsernameProblemLanguageResultExecution timeMemory
210144hanagasumiLong Distance Coach (JOI17_coach)C++17
0 / 100
30 ms29304 KiB
#include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <deque> #include <map> #include <set> #include <complex> #include <string> #include <unordered_map> #include <unordered_set> #include <random> #include <chrono> #define ft first #define sc second #define pb push_back #define len(v) (int)v.size() #define int ll using namespace std; typedef long long ll; typedef long double ld; int inf = (1LL << 62); const int N = (1 << 18); struct line { int k, b; int get(int x) { return k * x + b; } bool operator < (const line& x) const { return k < x.k; } }; struct node { node* l; node* r; line now; node(node* _l, node* _r, line _now) : l(_l), r(_r), now(_now) {} }; struct lichao { node* v; lichao() { v = new node(NULL, NULL, {0, inf}); } int get(node* v, int l, int r, int x) { int ans = v->now.get(x); int m = (l + r) / 2; if(m <= x) { if(v->r == NULL) return ans; else return min(ans, get(v->r, m, r, x)); } else { if(v->l == NULL) return ans; else return min(ans, get(v->l, l, m, x)); } } void upd(node* v, int l, int r, line val) { int m = (l + r) / 2; bool lft = val.get(l) < v->now.get(l); bool mid = val.get(m) < v->now.get(m); if(mid) swap(v->now, val); if(r - l == 1) return; if(lft == mid) { if(v->r == NULL) { auto neww = new node(NULL, NULL, {0, inf}); v->r = neww; } upd(v->r, m, r, val); return; } else { if(v->l == NULL) { auto neww = new node(NULL, NULL, {0, inf}); v->l = neww; } upd(v->l, l, m, val); return; } } int get(int x) { return get(v, 0, inf, x); } void upd(line val) { upd(v, 0, inf, val); } }; lichao tree[2 * N]; int get(int v, int l, int r, int vl, int vr, int X) { if(r <= vl || vr <= l) return inf; if(vl <= l && r <= vr) { return tree[v].get(X); } int m = (l + r) / 2; return min(get(v * 2, l, m, vl, vr, X), get(v * 2 + 1, m, r, vl, vr, X)); } void upd(int v, line val) { if(v == 0) return; tree[v].upd(val); upd(v / 2, val); return; } signed main() { #ifdef PC freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int x, n, m, w, T; cin >> x >> n >> m >> w >> T; vector<int> s(n + 1); vector<pair<int, int>> p(m); vector<int> pref(m + 1, 0); vector<int> cnt(m + 1, 0); vector<int> d(m + 1, 0); s[0] = 0; for (int i = 1; i <= n; i++) cin >> s[i]; s.pb(x); n += 2; sort(s.begin(), s.end()); for (int i = 0; i < m; i++) { cin >> p[i].ft >> p[i].sc; } sort(p.begin(), p.end()); for (int i = 0; i < m; i++) { pref[i + 1] = pref[i] + p[i].sc; cnt[i] = (x - p[i].ft) / T + 1; d[i] = p[i].ft; } vector<vector<pair<int, int>>> can(m + 1); for (int i = 1; i < n; i++) { int driver = s[i] / T * T; int lstt = -1, lst = -1; for (int j = 0; j < m; j++) { int time = s[i] / T * T + d[j]; if(time > s[i]) time -= T; if(time < s[i - 1]) continue; if(time < driver) continue; if(time > lstt) { lstt = time; lst = j; } } if(lstt == -1) continue; int minn = lst; for (int j = m - 1; j >= 0; j--) { int time = s[i] / T * T + d[j]; if(time > s[i]) time -= T; if(time < s[i - 1]) continue; if(time < driver) continue; minn = min(j, minn); // can[lst].pb({s[i], j}); } can[lst].pb({s[i], minn}); } vector<int> dp(m + 1, 0); for (int i = 0; i < m; i++) { dp[i + 1] = dp[i] + cnt[i] * w; upd(N + i, {-i, -pref[i] + dp[i]}); for (auto x : can[i]) { int time = x.ft / T * T + d[i]; if(time > x.ft) time -= T; int X = time / T * w; dp[i + 1] = min(dp[i + 1], pref[i + 1] + (i + 1) * X + get(1, 0, N, x.sc, i + 1, X)); } } cout << dp[m] + ((x / T + 1) * w) << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...