| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 463854 |
2021-08-11T22:24:15 Z |
rainboy |
Gauss (COCI17_gauss) |
C |
|
1002 ms |
90780 KB |
#include <stdio.h>
#include <string.h>
#define N 50
#define M 1000
#define C 10000
#define A 1000000
#define K 20 /* K = ceil(log2(A)) */
#define INF 0x3f3f3f3f
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int min(int a, int b) { return a < b ? a : b; }
int dd[A + 1], kk[A + 1], dp[A + 1][K + 1];
void init() {
int a, b;
for (a = 1; a <= A; a++)
for (b = a; b <= A; b += a) {
dd[b]++;
if (dd[a] == 2) {
int b_ = b;
while (b_ % a == 0)
b_ /= a, kk[b]++;
}
}
}
int cc[N];
int compare_a(int a, int b) { return a - b; }
int compare_c(int i, int j) { return cc[i] - cc[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 xx[N], yy[N];
long long cross(int i, int j, int k) {
return (long long) (xx[j] - xx[i]) * (yy[k] - yy[i]) - (long long) (xx[k] - xx[i]) * (yy[j] - yy[i]);
}
long long eval(int i, int x) {
return (long long) xx[i] * x + yy[i];
}
int main() {
static int aa[N], ii[N], ll[M], ff[C + 1], dq[K + 1], dr[K + 1], qu[N];
int n, m, d, q, h, h_, i, a, b, c, k, cnt;
init();
scanf("%d", &d);
for (c = 1; c <= d; c++)
scanf("%d", &ff[c]);
scanf("%d", &m);
for (h = 0; h < m; h++)
scanf("%d", &ll[h]);
compare = compare_a, sort(ll, 0, m);
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d%d", &aa[i], &cc[i]);
ii[i] = i;
}
compare = compare_c, sort(ii, 0, n);
for (a = 1; a <= A; a++)
memset(dp[a], 0x3f, (kk[a] + 1) * sizeof *dp[a]);
dp[1][0] = 0;
for (a = 1; a <= A; a++)
for (b = a + a; b <= A; b += a)
for (k = 0; k <= kk[a]; k++)
dp[b][k + 1] = min(dp[b][k + 1], dp[a][k] + (dd[b / a] > d ? 0 : ff[dd[b / a]]));
scanf("%d", &q);
while (q--) {
int k1, k2;
long long ans;
scanf("%d%d", &a, &b);
if (a % b != 0) {
printf("%d\n", -m);
continue;
}
for (k = 0; k <= kk[a / b]; k++)
dr[k] = dp[a / b][k];
cnt = 0;
for (i = 0; i < n; i++) {
int i_ = ii[i];
if (a % aa[i_] == 0 && aa[i_] % b == 0) {
int a_, b_, x;
a_ = a / aa[i_], b_ = aa[i_] / b;
memset(dq, 0x3f, (kk[a / b] + 1) * sizeof *dq);
for (k1 = 0; k1 <= kk[a_]; k1++)
for (k2 = 0; k2 <= kk[b_]; k2++)
dq[k1 + k2] = min(dq[k1 + k2], dp[a_][k1] + dp[b_][k2]);
x = INF;
for (k = 0; k <= kk[a / b]; k++)
dr[k] = min(dr[k], x = min(x + cc[i_], dq[k]));
if (x != INF) {
xx[i_] = cc[i_], yy[i_] = x - kk[a / b] * cc[i_];
while (1)
if (cnt == 0) {
qu[cnt++] = i_;
break;
} else if (xx[i_] == xx[qu[cnt - 1]]) {
if (yy[i_] < yy[qu[cnt - 1]])
cnt--;
else
break;
} else {
if (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) <= 0)
cnt--;
else {
qu[cnt++] = i_;
break;
}
}
}
}
}
ans = 0;
for (h = 0, h_ = cnt - 1; h < m; h++) {
k = ll[h];
if (k <= kk[a / b])
ans += dr[k] == INF ? -1 : dr[k];
else {
long long x = INF;
for (h_ = 0; h_ < cnt; h_++)
x = min(x, eval(qu[h_], k));
ans += x == INF ? -1 : x;
}
}
printf("%lld\n", ans);
}
return 0;
}
Compilation message
gauss.c: In function 'main':
gauss.c:80:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d", &d);
| ^~~~~~~~~~~~~~~
gauss.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d", &ff[c]);
| ^~~~~~~~~~~~~~~~~~~
gauss.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%d", &m);
| ^~~~~~~~~~~~~~~
gauss.c:85:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | scanf("%d", &ll[h]);
| ^~~~~~~~~~~~~~~~~~~
gauss.c:87:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
gauss.c:89:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%d%d", &aa[i], &cc[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
gauss.c:100:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
100 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
gauss.c:105:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d%d", &a, &b);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
659 ms |
90280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
692 ms |
90280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
680 ms |
90280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
672 ms |
90296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
804 ms |
90684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
806 ms |
90696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
774 ms |
90780 KB |
Output is correct |
| 2 |
Incorrect |
1002 ms |
90732 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
915 ms |
90660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
992 ms |
90668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
915 ms |
90676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
