#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef long double ld;
typedef pair <ld, ld> pdd;
const int N = 2e5 + 7;
ll h, n, m, w, t;
ll g[N], c[N], d[N], dp[N], psh[N], pref[N], po[N];
vector <pair <ll, pii> > v;
bool ccw(pdd x, pdd y, pdd z) {return x.F*(y.S-z.S)+y.F*(z.S-x.S)+z.F*(x.S-y.S) > 0;}
int main () {
FIO;
cin >> h >> n >> m >> w >> t;
for (int i = 0; i < n; i++) cin >> g[i];
g[n++] = h;
for (int i = 0; i < m; i++) cin >> d[i] >> c[i];
for (int i = 0; i < n; i++) {
v.pb({g[i]%t, {i, 0}});
}
for (int i = 0; i < m; i++) {
v.pb({d[i], {i, 1}});
}
sort(all(v));
vector <pair <int, pdd> > u;
ll la = 0, sh = h/t+1;
psh[0] = sh;
for (int i = 0; i < n+m; i++) {
psh[i+1] = psh[i];
pref[i+1] = pref[i];
po[i+1] = po[i];
int z = v[i].S.F;
if (!v[i].S.S) {
dp[i] = la;
if (z == n-1) sh--;
ll R = g[z]/t;
auto f = [&](int x) {return dp[x]+pref[i+1]-pref[x]+R*w*(po[i+1]-po[x])-(psh[i+1]-psh[x])*w;};
if (u.empty()) continue;
int lo = 0, hi = u.size()-1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (f(u[mid].F) < f(u[mid+1].F)) hi = mid;
else lo = mid+1;
}
dp[i] = min(dp[i], f(u[lo].F));
la = dp[i];
}
else {
po[i+1]++;
psh[i+1] += sh;
pref[i+1] += c[z];
dp[i] = la;
pdd p = {-po[i], dp[i]-pref[i]+psh[i]*w};
while (u.size() > 1 && !ccw(u[u.size()-2].S, u.back().S, p)) u.pop_back();
u.pb({i, p});
}
}
cout << dp[n+m-1]+psh[n+m]*w << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
8536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 3 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 4 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 5 |
Correct |
1 ms |
8540 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
