#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
#define int ll
const int N = 2e5 + 10;
const ll BINF = 1e18 + 10;
int can[N], dp[N], f[N], cost[N];
int t[4 * N], ps[4 * N];
void build(int v, int l, int r) {
t[v] = BINF;
ps[v] = -1;
if (l == r) {
return;
}
int mid = (l + r) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
}
void push(int v, int len1, int len2) {
if (ps[v] != -1) {
ps[2 * v] = ps[2 * v + 1] = ps[v];
t[2 * v] = ps[v] * len1;
t[2 * v + 1] = ps[v] * len2;
ps[v] = -1;
return;
}
}
void update(int v, int l, int r, int a, int b, int val) {
if (l > b || r < a) {
return;
}
if (l >= a && r <= b) {
t[v] = val * (r - l + 1);
ps[v] = val;
return;
}
int mid = (l + r) / 2;
push(v, mid - l + 1, r - mid);
update(2 * v, l, mid, a, b, val);
update(2 * v + 1, mid + 1, r, a, b, val);
t[v] = t[2 * v] + t[2 * v + 1];
}
int get_sum(int v, int l, int r, int a, int b) {
if (l > b || r < a) {
return 0;
}
if (l >= a && r <= b) {
return t[v];
}
int mid = (l + r) / 2;
push(v, mid - l + 1, r - mid);
return get_sum(2 * v, l, mid, a, b) + get_sum(2 * v + 1, mid + 1, r, a, b);
}
pair<int, int> t2[4 * N];
void build2(int v, int l, int r) {
if (l == r) {
t2[v] = {0, l};
return;
}
int mid = (l + r) / 2;
build2(2 * v, l, mid);
build2(2 * v + 1, mid + 1, r);
t2[v] = max(t2[2 * v], t2[2 * v + 1]);
}
void update2(int v, int l, int r, int pos, int val) {
if (l == r) {
t2[v] = {val, pos};
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
update2(2 * v, l, mid, pos, val);
}
else {
update2(2 * v + 1, mid + 1, r, pos, val);
}
t2[v] = max(t2[2 * v], t2[2 * v + 1]);
}
pair<int, int> get_max(int v, int l, int r, int a, int b) {
if (l > b || r < a) {
return {0, 0};
}
if (l >= a && r <= b) {
return t2[v];
}
int mid = (l + r) / 2;
return max(get_max(2 * v, l, mid, a, b), get_max(2 * v + 1, mid + 1, r, a, b));
}
int pref[N], prv[N];
inline int get_sum(int l, int r) {
return pref[r] - pref[l - 1];
}
set<int> good;
int w, x, n, m;
inline bool check(int x) {
auto it = ++good.lower_bound(x);
if (it == good.end()) {
update2(1, 1, m, x, 0);
return false;
}
if (dp[x] + get_sum(x + 1, *it) + w * get_sum(1, 1, m, x + 1, *it) <= dp[*it]) {
good.erase(it);
check(x);
return true;
}
else {
if (dp[*it] - dp[x] - get_sum(x + 1, *it) < 0) {
assert(false);
update2(1, 1, m, x, -1);
}
else {
update2(1, 1, m, x, (dp[*it] - dp[x] - get_sum(x + 1, *it)) / (w * (*it - x)));
}
return false;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> x >> n >> m >> w >> t;
vector<int> s(n);
for (auto &it : s) {
cin >> it;
}
sort(all(s));
vector<pair<int, int>> srt;
for (int i = 1; i <= m; i++) {
cin >> f[i] >> cost[i];
srt.pb({f[i], i});
}
sort(all(srt));
for (int i = 0; i <= m; i++) {
can[i] = BINF;
}
for (auto it : s) {
int ps = lower_bound(all(srt), make_pair(it % t, 0ll)) - srt.begin();
if (ps + 1 <= m) {
can[ps + 1] = min(can[ps + 1], it / t);
}
else {
can[0] = min(can[0], it / t);
}
}
int ps = lower_bound(all(srt), make_pair(x % t, 0ll)) - srt.begin();
if (ps + 1 <= m) {
can[ps + 1] = min(can[ps + 1], x / t);
}
else {
can[0] = min(can[0], x / t);
}
for (int i = 1; i <= m; i++) {
pref[i] = pref[i - 1] + cost[srt[i - 1].S];
}
vector<pair<int, int>> st;
for (int i = 1; i <= m; i++) {
while (!st.empty() && st.back().F > can[i]) {
st.pop_back();
}
if (!st.empty()) {
prv[i] = st.back().S;
}
else {
prv[i] = 1;
}
st.pb({can[i], i});
}
dp[0] = w * (x / t + 1);
good.insert(0);
build(1, 1, m);
build2(1, 1, m);
for (int i = 1; i <= m; i++) {
int cnt = x / t;
if (f[srt[i - 1].S] < x % t) {
cnt++;
}
dp[i] = dp[i - 1] + w * cnt;
if (can[i] < BINF) {
update(1, 1, m, prv[i], i - 1, can[i]);
for (;;) {
pair<int, int> kek = get_max(1, 1, m, prv[i] - 1, i - 1);
if (kek.F < can[i]) {
break;
}
if (!check(kek.S)) {
break;
}
}
auto it = good.lower_bound(prv[i] - 1);
if (it != good.begin()) {
check(*(--it));
}
int lst = *good.rbegin();
dp[i] = min(dp[i], dp[lst] + w * cnt + get_sum(lst + 1, i - 1) + w * get_sum(1, 1, m, lst + 1, i - 1));
}
good.insert(i);
if (SZ(good) > 1) {
check(*(----good.end()));
}
}
int ans = dp[m];
if (can[0] < BINF) {
int sum = 0, cl = can[0];
for (int lst = m - 1; lst >= 0; lst--) {
sum += w * cl + cost[srt[lst].S];
cl = min(cl, can[lst + 1]);
ans = min(ans, sum + dp[lst]);
}
}
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Runtime error |
7 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
