#include <stdio.h>
#define N 200000
#define M 200002
#define INF 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;
}
void sort(long long *xx, int l, int r) {
while (l < r) {
int i = l, j = l, k = r;
long long x = xx[l + rand_() % (r - l)], tmp;
while (j < k)
if (xx[j] == x)
j++;
else if (xx[j] < x) {
tmp = xx[i], xx[i] = xx[j], xx[j] = tmp;
i++, j++;
} else {
k--;
tmp = xx[j], xx[j] = xx[k], xx[k] = tmp;
}
sort(xx, l, i);
l = k;
}
}
int main() {
static int cc[N];
static long long rr[N], xx[M + 2];
int n, m, c, b, b_, i, j;
long long md, t, t1, t2, x_, ans, z;
scanf("%lld%d%d%d%lld", &x_, &m, &n, &c, &md), m += 2;
xx[0] = -1, xx[m - 1] = x_;
for (j = 1; j + 1 < m; j++)
scanf("%lld", &xx[j]);
sort(xx, 0, m);
for (i = 0; i < n; i++)
scanf("%lld%d", &rr[i], &cc[i]);
ans = INF;
for (b = 0; b < 1 << n; b++) {
z = 0;
for (i = 0; i < n; i++)
if ((b & 1 << i) == 0)
z += cc[i];
b_ = 0;
for (j = 1; j < m; j++) {
t = max(xx[j - 1], (xx[j] + md) / md * md - md);
for (i = 0; i < n; i++)
if ((b & 1 << i) != 0)
t = max(t, (xx[j] + md - rr[i]) / md * md - (md - rr[i]));
t1 = (xx[j - 1] + md) / md * md - md;
t2 = (xx[j] + md) / md * md - md;
z += (max(t2 - t1, 0) / md) * c;
for (i = 0; i < n; i++)
if ((b_ & 1 << i) == 0) {
t1 = (xx[j - 1] + md - rr[i]) / md * md - (md - rr[i]);
t2 = (xx[j] + md - rr[i]) / md * md - (md - rr[i]);
if (t1 < t2) {
z += (max(min(t, t2) - t1, 0) / md) * c;
if (t2 > t)
b_ |= 1 << i;
}
}
}
ans = min(ans, z);
}
printf("%lld\n", ans);
return 0;
}
Compilation message
coach.c: In function 'main':
coach.c:42:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%lld%d%d%d%lld", &x_, &m, &n, &c, &md), m += 2;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.c:45:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | scanf("%lld", &xx[j]);
| ^~~~~~~~~~~~~~~~~~~~~
coach.c:48:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%lld%d", &rr[i], &cc[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
292 KB |
Output is correct |
| 15 |
Correct |
1 ms |
312 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
292 KB |
Output is correct |
| 15 |
Correct |
1 ms |
312 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
292 KB |
Output is correct |
| 15 |
Correct |
1 ms |
312 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
292 KB |
Output is correct |
| 15 |
Correct |
1 ms |
312 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
212 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
1 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Incorrect |
1 ms |
292 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
