#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 = 289, M = 21, INF = 1e9, V = M * Z;
int f[N], len[N], lucky[L], price[L], 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];
map<vector<int>, int> mp;
vector<int> vec[N], st_vec[Z];
int pr_cnt = 0;
vector<int> cur;
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;
}
}
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];
}
cin >> t;
for (int i = 0; i < t; i++) {
cin >> lucky[i] >> price[i];
}
cin >> q;
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;
}
}
for (int j = 0; j < t; j++) {
if (lucky[j] % b == 0 && a % lucky[j] == 0) {
int x = lucky[j] / b;
for (int k = 0; k < M; k++) {
for (int h = k; h < M; h++) {
upd(small_ans[h], dp[state[x]][k][d][1] + price[j] * (h - k));
}
}
}
}
ll ans = 0;
for (int j = 0; j < m; j++) {
ans += (small_ans[len[j]] == INF ? -1 : small_ans[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:21: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(int, std::vector<int>&, int, int)':
gauss.cpp:56:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x == v.size()) {
~~^~~~~~~~~~~
gauss.cpp:83:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
gauss.cpp: In function 'int main()':
gauss.cpp:93:13: warning: unused variable 'start' [-Wunused-variable]
clock_t start = clock();
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
688 ms |
85732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
692 ms |
85836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
702 ms |
85932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
693 ms |
85952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2066 ms |
86476 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2051 ms |
86504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
86504 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
86348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2037 ms |
86552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
86732 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
