#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll MAXN = 2e5+1;
ll n, m, t, wint, wcost;
ll dp[MAXN];
pii ppl[MAXN]; // time, drop_cost
ll refill[MAXN];
ll stat_with[MAXN];
ll pre[MAXN];
bool skip[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 ((__int128)a.num*b.denom) < ((__int128)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);
}
ll sim(vector<int> &amounts) {
fill(skip, skip+n, 0);
int apos = 1;
int iter = 0;
int cur = 0;
int w = amounts[0];
ll cost = 0;
while (iter*wint+ppl[cur].first < t) {
while (apos < m && refill[apos-1] < iter*wint+ppl[cur].first) {
w += amounts[apos];
apos++;
}
if (!skip[cur]) {
if (w == 0) {
if (cur == 0) return -1;
skip[cur] = 1;
cost += ppl[cur].second;
}
else {
w--;
cost += wcost;
}
}
cur++;
if (cur == n) {
iter++;
cur = 0;
}
}
return cost;
}
ll opt(int pos, ll w_left, vector<int> &amounts) {
if (pos == m) return sim(amounts);
ll best = -1;
for (int a = 0; a <= w_left; a++) {
amounts.push_back(a);
ll cur = opt(pos+1, w_left-a, amounts);
amounts.pop_back();
if (cur != -1 && (best == -1 || cur < best)) best = cur;
}
return best;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> t >> m >> n >> wcost >> wint;
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;
ll mxw = 0;
for (ll i = 0; i < n; i++) {
cur += ppl[i].second;
pre[i] = cur;
mxw += (t-ppl[i].first)/wint + 1;
}
for (ll i = 0; i < m; i++) {
ll comp = refill[i]/wint;
ll mn = 0;
ll 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 (ll i = 1; i < n; i++) {
dp[i] = wcost*((t-ppl[i].first)/wint+1)+dp[i-1];
if (stat_with[i] >= 0) {
ll stat = stat_with[i];
ll sl = wcost*((refill[stat]-ppl[i].first)/wint);
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].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";
vector<int> v;
cout << opt(0, mxw, v) << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
