Submission #623550

#TimeUsernameProblemLanguageResultExecution timeMemory
623550flappybirdLong Distance Coach (JOI17_coach)C++17
100 / 100
214 ms41688 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define MAX 205050 #define MAXS 20 #define INF (ll)2e18 #define bb ' ' #define ln '\n' #define Ln '\n' #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif #define MOD 1000000007 struct Line { ll a, b; Line(ll a = 0, ll b = INF) :a(a), b(b) {} ll operator[](ll x) { return a * x + b; } }; struct segtree { struct Node { ll l, r; ll low, high; Line f; }; vector<Node> tree; segtree(ll l, ll r) { tree.push_back({ -1, -1, l, r, Line() }); } void upd(ll loc, Line f) { ll l, r; l = tree[loc].low; r = tree[loc].high; auto pv = tree[loc].f; if (f[l] > pv[l]) swap(f, pv); if (f[r] <= pv[r]) { tree[loc].f = f; return; } ll m = (l + r) >> 1; if (f[m] > pv[m]) { tree[loc].f = pv; if (!~tree[loc].l) { tree[loc].l = tree.size(); tree.push_back({ -1, -1, l, m, Line() }); } upd(tree[loc].l, f); } else { tree[loc].f = f; if (!~tree[loc].r) { tree[loc].r = tree.size(); tree.push_back({ -1, -1, m + 1, r, Line() }); } upd(tree[loc].r, pv); } } ll query(ll loc, ll x) { if (!~loc) return INF; ll m = (tree[loc].low + tree[loc].high) >> 1; if (x <= m) return min(query(tree[loc].l, x), tree[loc].f[x]); else return min(query(tree[loc].r, x), tree[loc].f[x]); } }; vector<ll> dps[MAX]; ll C[MAX]; ll dp[MAX]; ll S[MAX]; signed main() { ios::sync_with_stdio(false), cin.tie(0); ll N, M; ll W, X, T; cin >> X >> N >> M >> W >> T; ll i; ll a, b; vector<ll> s = { X }; for (i = 1; i <= N; i++) cin >> a, s.push_back(a); vector<pll> in; vector<ll> lst = { 0 }; for (i = 1; i <= M; i++) cin >> a >> b, in.emplace_back(a, b), lst.push_back(a); sort(in.begin(), in.end()); for (i = 1; i <= M; i++) C[i] = in[i - 1].second; sort(lst.begin(), lst.end()); for (auto x : s) dps[lower_bound(lst.begin(), lst.end(), x % T) - lst.begin() - 1].push_back(x / T); for (i = 1; i <= M; i++) S[i] = S[i - 1] + C[i]; segtree seg(1, M); for (i = M; i >= 1; i--) { for (auto v : dps[i]) seg.upd(0, Line(-v * W, v * W * (ll)(i + 1) + dp[i + 1] + S[i])); dp[i] = min(seg.query(0, i) - S[i - 1], dp[i + 1] + W * ((X - lst[i]) / T + 1)); } cout << dp[1] + W * (X / T + 1) << ln; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...