| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 597507 | GusterGoose27 | Long Distance Coach (JOI17_coach) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<ll, ll> pii;
typedef long long ll;
const ll MAXN = 2e5+1;
long long n, m, t, wll, wcost;
ll dp[MAXN];
pii ppl[MAXN]; // time, drop_cost
ll refill[MAXN];
ll stat_with[MAXN];
ll pre[MAXN];
const ll inf = 4e18;
class Frac {
public:
ll num, denom;
Frac() {
num = inf;
denom = 1;
}
Frac(ll x, ll y) {
num = x;
denom = y;
reduce();
}
void reduce() {
if (denom < 0) {
denom *= -1;
num *= -1;
}
ll g = gcd(abs(num), denom);
num /= g;
denom /= g;
}
ll gcd(ll a, ll b) {
if (a > b) return gcd(b, a);
if (a == 0) return b;
return gcd(b%a, a);
}
};
bool operator<(Frac a, Frac b) {
return ((__ll128)a.num*b.denom) < ((__ll128)b.num*a.denom);
}
class Line {
public:
ll ller;
ll slope;
Frac rbound;
Line(ll in, ll s) {
ller = in;
slope = s;
}
};
Frac llersect(Line a, Line b) {
return Frac(a.ller-b.ller, b.slope-a.slope);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> t >> m >> n >> wcost >> wll;
m++;
for (ll i = 0; i < m-1; i++) {
long long r; cin >> r;
refill[i] = r;
}
refill[m-1] = t;
sort(refill, refill+m);
n++;
ppl[0] = pii(0, 0);
for (ll i = 1; i < n; i++) {
ll x, y; cin >> x >> y;
ppl[i] = pii(x, y);
}
sort(ppl, ppl+n);
fill(stat_with, stat_with+n, -1);
ll cur = 0;
for (ll i = 0; i < n; i++) {
cur += ppl[i].second;
pre[i] = cur;
}
for (ll i = 0; i < m; i++) {
ll comp = refill[i]/wll;
ll mn = 0;
ll mx = n;
while (mx > mn+1) {
ll cur = (mn+mx)/2;
if ((refill[i]-ppl[cur].first)/wll == comp) mn = cur;
else mx = cur;
}
if (stat_with[mn] == -1) stat_with[mn] = i;
}
dp[0] = wcost*((t+wll)/wll);
vector<Line> hull;
hull.push_back(Line(dp[0]-pre[0], 0));
for (ll i = 1; i < n; i++) {
dp[i] = wcost*((t-ppl[i].first)/wll+1)+dp[i-1];
if (stat_with[i] >= 0) {
ll stat = stat_with[i];
ll sl = wcost*((refill[stat]-ppl[i].first)/wll);
ll mn = -1;
ll mx = hull.size()-1;
Frac f(sl, 1);
while (mx > mn+1) {
ll cur = (mn+mx)/2;
if (hull[cur].rbound < f) mn = cur;
else mx = cur;
}
ll cval = pre[i]+hull[mx].ller+hull[mx].slope*sl+i*sl;
dp[i] = min(dp[i], cval);
}
Line cur_l(dp[i]-pre[i], -i);
Frac ller = llersect(cur_l, hull.back());
while (hull.size() > 1 && ller < hull[hull.size()-2].rbound) {
hull.pop_back();
ller = llersect(cur_l, hull.back());
}
hull.back().rbound = ller;
hull.push_back(cur_l);
}
cout << dp[n-1] << "\n";
}