#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#define int long long
const int N = 1e6 + 5, L = 55, P = 10, Z = 289, M = 21, INF = 1e18, V = M * Z;
int f[N], len[N], state[N], gg[N], ww[N], sum[Z],
divisor[N], primes[10], dp[Z][M][Z][2], ans[N], small_ans[M], best[L][M];
pair<int, int> lucky[L];
vector<int> vec[N], st_vec[Z], cur;
int pr_cnt = 0;
int trie[V][M], num[V];
int cv = 1, cnt = 0;
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 = 0;
for (int i = 0; i < x; i++) {
if (trie[v][cur[i]] == -1)
trie[v][cur[i]] = cv++;
v = trie[v][cur[i]];
}
if (num[v] == -1) {
num[v] = cnt;
sum[cnt] = s;
st_vec[cnt] = cur;
cnt++;
}
cur.push_back(1);
prod *= primes[x];
while (prod < N && cur[x] <= last) {
rec(x + 1, cur[x], prod, s + cur[x]);
cur[x]++;
prod *= primes[x];
}
cur.pop_back();
}
void upd(int &a, int b) {
a = min(a, b);
}
ll 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 < Z; i++) {
for (int j = 0; j <= sum[from]; j++) {
upd(dp[i][j + 1][to][to == i], dp[i][j][from][0] + f[prod]);
upd(dp[i][j + 1][to][1], dp[i][j][from][1] + 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();
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;
}
}
memset(num, -1, sizeof(num));
memset(trie, -1, sizeof(trie));
rec(0, INF, 1, 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]);
}
int n, m, t, q;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
for (int x = 0; x < Z; x++) {
for (int y = 0; y < M; y++) {
for (int z = 0; z < Z; z++) {
dp[x][y][z][0] = dp[x][y][z][1] = INF;
}
}
dp[x][0][0][x == 0] = 0;
}
for (int i = 0; i < cnt; i++) {
rec_dp(0, st_vec[i], 1, i);
}
// vector<int> v1 = { 1 };
// int xx = getId(v1);
// cout << dp[100][1][xx][0];
// return 0;
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);
cin >> q;
CHT cht;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
if (a % b) {
cout << -m << "\n";
continue;
}
fill(small_ans, small_ans + M, INF);
int d = state[a / b];
for (int x = 0; x < Z; x++) {
for (int y = 0; y < M; y++) {
upd(small_ans[y], dp[x][y][d][0]);
upd(small_ans[y], dp[x][y][d][1]);
}
}
for (int x = 0; x < t; x++) {
for (int y = 0; y < M; y++) {
best[x][y] = INF;
}
}
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, mn = INF;
for (int k = 0; k < M; k++) {
for (int h = k; h < M; h++) {
upd(small_ans[h], dp[state[x]][k][d][1] + lucky[j].first * (h - k));
}
mn = min(mn, dp[state[x]][k][d][1] - k * lucky[j].first);
}
// cout << lucky[j].first << " " << mn << "\n";
if (mn != INF)
cht.addLine({ lucky[j].first, mn });
}
}
// for (Line a : cht) {
// cout << a.k << " " << a.b << " " << a.lx << "\n";
// }
ll ans = 0;
for (int j = 0; j < m; j++) {
if (len[j] < M) {
ans += (small_ans[len[j]] == INF ? -1 : 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 'long long int getId(const std::vector<long long int>&)':
gauss.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < v.size(); i++) {
~~^~~~~~~~~~
gauss.cpp: In function 'long long int rec_dp(long long int, std::vector<long long int>&, long long int, long long int)':
gauss.cpp:59:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x == v.size()) {
~~^~~~~~~~~~~
gauss.cpp:86:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
gauss.cpp: In member function 'long long int CHT::que(long long int)':
gauss.cpp:136:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (pos + 1 < size() && (begin() + pos + 1)->lx <= x)
~~~~~~~~^~~~~~~~
gauss.cpp: In function 'int main()':
gauss.cpp:156:13: warning: unused variable 'start' [-Wunused-variable]
clock_t start = clock();
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
977 ms |
129644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1010 ms |
129664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
986 ms |
129632 KB |
Output is correct |
| 2 |
Correct |
1097 ms |
129812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
995 ms |
129728 KB |
Output is correct |
| 2 |
Correct |
989 ms |
129748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
130196 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
130104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
130088 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2017 ms |
130012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2053 ms |
129976 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2095 ms |
129952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
