#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
const int N = 1e6 + 5, L = 55, P = 10, Z = 300, M = 21, INF = 1e9;
int f[N], len[N], state[N], gg[N], ww[N], sum[Z],
divisor[N], primes[10], dp[M][Z], small_ans[M],
trie[Z][M], num[Z];
int pr_cnt = 0, cv = 1, cnt = 0;
pair<int, int> lucky[L];
vector<int> vec[N], st_vec[Z], cur;
int getId(const vector<int> &v) {
int ver = 0;
for (int i = 0; i < v.size(); i++) {
ver = trie[ver][v[i]];
}
return num[ver];
}
void rec(int x, int last, int prod, int s, int v) {
num[v] = cnt;
sum[cnt] = s;
st_vec[cnt] = cur;
cnt++;
cur.push_back(1);
prod *= primes[x];
while (prod < N && cur[x] <= last) {
trie[v][cur[x]] = cv++;
rec(x + 1, cur[x], prod, s + cur[x], trie[v][cur[x]]);
cur[x]++;
prod *= primes[x];
}
cur.pop_back();
}
void upd(int &a, int b) {
a = min(a, b);
}
void rec_dp(int x, vector<int> &v, int prod, int to) {
if (x == v.size()) {
if (prod > 1) {
vector<int> s = v;
sort(s.rbegin(), s.rend());
while (!s.empty() && s.back() == 0)
s.pop_back();
int from = getId(s);
for (int i = 0; i <= sum[from]; i++) {
upd(dp[i + 1][to], dp[i][from] + f[prod]);
}
}
}
else {
int d = 0, tmp = v[x];
while (v[x] >= 0) {
rec_dp(x + 1, v, prod * (d + 1), to);
v[x]--;
d++;
}
v[x] = tmp;
}
}
struct Line {
ll k, b;
double lx;
};
struct CHT : vector<Line> {
bool bad(iterator y) {
if (y == begin()) {
if (next(y) == end())
return false;
auto z = next(y);
return z->k == y->k && z->b <= y->b;
}
if (next(y) == end()) {
auto x = prev(y);
return x->k == y-> k && x->b <= y->b;
}
auto x = prev(y), z = next(y);
return (y->b - x->b) * (double)(y->k - z->k) >=
(z->b - y->b) * (double)(x->k - y->k);
}
void calcLx(iterator y) {
if (y == begin()) {
y->lx = -INF;
}
else {
auto x = prev(y);
y->lx = (x->b - y->b) / (double)(y->k - x->k);
}
}
void addLine(Line a) {
push_back(a);
if (bad(end() - 1)) {
pop_back();
return;
}
while (size() > 1 && bad(end() - 2)) {
erase(end() - 2);
}
calcLx(end() - 1);
}
int pos = 0;
int que(int x) {
while (pos + 1 < size() && (begin() + pos + 1)->lx <= x)
pos++;
auto opt = begin() + pos;
return opt->k * x + opt->b;
}
void cl() {
clear();
pos = 0;
}
};
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
// clock_t start = clock();
int n, m, t, q;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> len[i];
}
sort(len, len + m);
cin >> t;
for (int i = 0; i < t; i++) {
cin >> lucky[i].second >> lucky[i].first;
}
sort(lucky, lucky + t);
reverse(lucky, lucky + t);
// end of input reading
for (int i = 2; i * i < N; i++) {
if (!divisor[i]) {
for (int j = i * i; j < N; j += i) {
divisor[j] = divisor[j] ? min(divisor[j], i) : i;
}
}
}
for (int i = 2; i < N; i++) {
if (!divisor[i]) {
divisor[i] = i;
if (pr_cnt < P)
primes[pr_cnt++] = i;
}
}
// for (int i = 0; i < pr_cnt; i++) {
// cout << primes[i] << "\n";
// }
memset(num, -1, sizeof(num));
memset(trie, -1, sizeof(trie));
rec(0, INF, 1, 0, 0);
for (int i = 2; i < N; i++) {
int x = i / divisor[i], y = 1;
if (divisor[x] == divisor[i]) {
y += ww[x];
x = gg[x];
}
gg[i] = x;
ww[i] = y;
vec[i] = vec[x];
vec[i].push_back(y);
}
for (int i = 1; i < N; i++) {
sort(vec[i].rbegin(), vec[i].rend());
state[i] = getId(vec[i]);
}
for (int x = 0; x < M; x++) {
for (int j = 0; j < Z; j++) {
dp[x][j] = INF;
}
}
dp[0][0] = 0;
for (int i = 0; i < cnt; i++) {
rec_dp(0, st_vec[i], 1, i);
}
cin >> q;
CHT cht;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
ll ans = 0;
if (a % b) {
ans = -m;
}
else {
fill(small_ans, small_ans + M, INF);
int d = state[a / b];
for (int x = 0; x < M; x++) {
upd(small_ans[x], dp[x][d]);
}
cht.cl();
for (int j = 0; j < t; j++) {
if (lucky[j].second % b == 0 && a % lucky[j].second == 0) {
int x = lucky[j].second / b, y = a / lucky[j].second, mn = INF;
x = state[x];
y = state[y];
for (int k = 0; k <= sum[x]; k++) {
for (int h = 0; h <= sum[y]; h++) {
if (dp[k][x] != INF && dp[h][y] != INF) {
for (int z = 0; z + k + h < M; z++) {
upd(small_ans[k + h + z], dp[k][x] + dp[h][y] + lucky[j].first * z);
}
upd(mn, dp[k][x] + dp[h][y] - lucky[j].first * (k + h));
}
}
}
if (mn != INF)
cht.addLine({ lucky[j].first, mn });
}
}
for (int j = 0; j < m; j++) {
if (len[j] < M) {
if (small_ans[len[j]] == INF)
ans--;
else
ans += small_ans[len[j]];
}
else if (cht.empty()) {
ans--;
}
else {
ans += cht.que(len[j]);
}
}
}
cout << ans << "\n";
}
// cout << (clock() - start) / (double)CLOCKS_PER_SEC;
return 0;
}
Compilation message
gauss.cpp: In function 'int getId(const std::vector<int>&)':
gauss.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
gauss.cpp: In function 'void rec_dp(int, std::vector<int>&, int, int)':
gauss.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x == v.size()) {
~~^~~~~~~~~~~
gauss.cpp: In member function 'int CHT::que(int)':
gauss.cpp:121:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (pos + 1 < size() && (begin() + pos + 1)->lx <= x)
~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
340 ms |
71672 KB |
Output is correct |
| 2 |
Correct |
377 ms |
71640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
341 ms |
71540 KB |
Output is correct |
| 2 |
Correct |
338 ms |
71544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
341 ms |
71620 KB |
Output is correct |
| 2 |
Correct |
338 ms |
71552 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
348 ms |
71632 KB |
Output is correct |
| 2 |
Correct |
330 ms |
71668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
470 ms |
72588 KB |
Output is correct |
| 2 |
Correct |
430 ms |
72568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
411 ms |
72524 KB |
Output is correct |
| 2 |
Correct |
493 ms |
72532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
409 ms |
72600 KB |
Output is correct |
| 2 |
Correct |
541 ms |
72556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
539 ms |
72532 KB |
Output is correct |
| 2 |
Correct |
459 ms |
72404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
507 ms |
72440 KB |
Output is correct |
| 2 |
Correct |
426 ms |
72456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
471 ms |
72532 KB |
Output is correct |
| 2 |
Correct |
485 ms |
72504 KB |
Output is correct |
