#include <stdio.h>
#define N 200002
#define M 200002
#define LINF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long xx[M], xx_[M]; int ll[M], rr[M], jj[M], m;
int compare_x(int i, int j) {
return xx[i] == xx[j] ? 0 : (xx[i] < xx[j] ? -1 : 1);
}
long long uu[N]; int cc[N], ii[N], n;
int compare_u(int i, int j) {
return uu[i] == uu[j] ? 0 : (uu[i] < uu[j] ? -1 : 1);
}
int compare_r(int i, int j) {
return rr[i] - rr[j];
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int search(long long u) {
int lower = -1, upper = n;
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (uu[ii[i]] <= u)
lower = i;
else
upper = i;
}
return lower;
}
int main() {
static long long tt[N], dp[N];
int i, i_, j, j_;
long long md, w, x_, x, y, z, ans;
scanf("%lld%d%d%lld%lld", &x_, &m, &n, &w, &md), n++, m += 2;
xx[0] = -1, xx[m - 1] = x_;
for (j = 1; j + 1 < m; j++)
scanf("%lld", &xx[j]);
for (j = 0; j < m; j++)
jj[j] = j;
compare = compare_x, sort(jj, 0, m);
for (j = 0; j < m; j++)
xx_[j] = xx[jj[j]];
for (j = 0; j < m; j++)
xx[j] = xx_[j];
uu[0] = 0;
for (i = 1; i < n; i++)
scanf("%lld%d", &uu[i], &cc[i]);
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_u, sort(ii, 0, n);
dp[0] = 0;
for (j = 1; j < m; j++) {
x = xx[j - 1], y = xx[j];
ll[j] = search(y % md - (y - x)) + 1, rr[j] = search(y % md);
}
for (j = 1; j < m; j++)
jj[j - 1] = j;
compare = compare_r, sort(jj, 0, m - 1);
for (i = 0; i < n; i++)
tt[i] = (x_ + md - uu[ii[i]]) / md;
for (i = 0, j = 0; i < n; i++) {
if (i == 0)
dp[i] = ((x_ + md - uu[ii[i]]) / md) * w;
else {
dp[i] = LINF;
z = 0;
for (i_ = i - 1; i_ >= 0; i_--) {
dp[i] = min(dp[i], dp[i_] + z);
z += tt[i_] * w + cc[ii[i_]];
}
dp[i] += ((x_ + md - uu[ii[i]]) / md) * w;
}
while (j < m - 1 && rr[j_ = jj[j]] == i) {
j++;
for (i_ = ll[j_]; i_ <= rr[j_]; i_++)
tt[i_] = min(tt[i_], (xx[j_] + md - uu[i_]) / md - 1);
}
}
ans = LINF, z = 0;
for (i_ = n - 1; i_ >= 0; i_--) {
ans = min(ans, dp[i_] + z);
z += tt[i_] * w + cc[ii[i_]];
}
printf("%lld\n", ans);
return 0;
}
Compilation message
coach.c: In function 'main':
coach.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%lld%d%d%lld%lld", &x_, &m, &n, &w, &md), n++, m += 2;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%lld", &xx[j]);
| ^~~~~~~~~~~~~~~~~~~~~
coach.c:88:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%lld%d", &uu[i], &cc[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
