#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 2e5+1;
ll n, m, t, wint, wcost;
ll dp[MAXN];
pii ppl[MAXN]; // time, drop_cost
ll refill[MAXN];
int 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 a.num*b.denom < b.num*a.denom;
}
class Line {
public:
ll inter;
ll slope;
Frac rbound;
Line(ll in, ll s) {
inter = in;
slope = s;
}
};
Frac intersect(Line a, Line b) {
return Frac(a.inter-b.inter, b.slope-a.slope);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> t >> m >> n >> wcost >> wint;
m++;
for (int i = 0; i < m-1; i++) cin >> refill[i];
refill[m-1] = t;
n++;
ppl[0] = pii(0, 0);
for (int i = 1; i < n; i++) {
int 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 (int i = 0; i < n; i++) {
cur += ppl[i].second;
pre[i] = cur;
}
for (int i = 0; i < m; i++) {
ll comp = refill[i]/wint;
int mn = 0;
int mx = n;
while (mx > mn+1) {
ll cur = (mn+mx)/2;
if ((refill[i]-ppl[cur].first)/wint == comp) mn = cur;
else mx = cur;
}
if (stat_with[mn] == -1) stat_with[mn] = i;
}
dp[0] = wcost*(t/wint+1);
vector<Line> hull;
hull.push_back(Line(dp[0]-pre[0], 0));
for (int i = 1; i < n; i++) {
dp[i] = wcost*((t-ppl[i].first)/wint+1)+dp[i-1];
if (stat_with[i] >= 0) {
int stat = stat_with[i];
ll sl = wcost*((refill[stat]-ppl[i].first)/wint);
int mn = -1;
int mx = hull.size()-1;
Frac f(sl, 1);
while (mx > mn+1) {
int cur = (mn+mx)/2;
if (hull[cur].rbound < f) mn = cur;
else mx = cur;
}
ll cval = pre[i]+hull[mx].inter+hull[mx].slope*sl+i*sl;
dp[i] = min(dp[i], cval);
}
Line cur_l(dp[i]-pre[i], -i);
Frac inter = intersect(cur_l, hull.back());
while (hull.size() > 1 && inter < hull[hull.size()-2].rbound) {
hull.pop_back();
inter = intersect(cur_l, hull.back());
}
hull.back().rbound = inter;
hull.push_back(cur_l);
}
cout << dp[n-1] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
