#include <bits/stdc++.h>
using namespace std;
int MAX = 1e6, MAX_SUM_EXP = 20;
vector <int> numDivisor(MAX + 1, 0);
vector <int> sumExponent(MAX + 1, 0);
const int INF = 1e9 + 20;
void sieve() {
for (int divisor = 1; divisor <= MAX; divisor++) {
for (int multiplier = divisor; multiplier <= MAX; multiplier += divisor) {
numDivisor[multiplier] += 1;
if (numDivisor[divisor] == 2) {
int temp = multiplier;
do {
sumExponent[multiplier]++;
temp /= divisor;
} while (temp % divisor == 0);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k;
cin >> k;
vector <int> listPricePath(k);
for (int i = 0; i < k; i++)
cin >> listPricePath[i];
int numQueriesLength;
cin >> numQueriesLength;
vector <int> listLength(numQueriesLength);
for (int indexOfLength = 0; indexOfLength < numQueriesLength; indexOfLength++)
cin >> listLength[indexOfLength];
int numQueriesLuckyNumber;
cin >> numQueriesLuckyNumber;
vector <int> listLuckyNumber(numQueriesLuckyNumber);
vector <int> listCostLuckyNumber(numQueriesLuckyNumber);
for (int indexOfLuckyNumber = 0; indexOfLuckyNumber < numQueriesLuckyNumber; indexOfLuckyNumber++)
cin >> listLuckyNumber[indexOfLuckyNumber] >> listCostLuckyNumber[indexOfLuckyNumber];
sieve();
// shortestPathTo1[i][j] = Shortest path from i to 1 known that sum of exp = j
vector <vector <int>> shortestPathTo1(MAX + 1, vector <int> (MAX_SUM_EXP + 2, INF));
shortestPathTo1[1][0] = 0;
for (int divisor = 1; divisor <= MAX; divisor++) {
for (int multiplier = 2 * divisor, base = 2; multiplier <= MAX; multiplier += divisor, base++) {
for (int sumOfExp = 0; sumOfExp <= sumExponent[divisor]; sumOfExp++)
shortestPathTo1[multiplier][sumOfExp + 1]
= min(shortestPathTo1[multiplier][sumOfExp + 1],
shortestPathTo1[divisor][sumOfExp] + (numDivisor[base] <= k ? listPricePath[numDivisor[base] - 1] : 0));
}
}
int numQueriesAnswer, firstNumber, secondNumber;
cin >> numQueriesAnswer;
for (int indexOfQueries = 1; indexOfQueries <= numQueriesAnswer; indexOfQueries++) {
cin >> firstNumber >> secondNumber;
if (firstNumber % secondNumber != 0) {
cout << (-1 * numQueriesLength);
continue;
}
int compressSource = firstNumber / secondNumber;
// d(A, B) = d(A / B, 1) without using option 2: Leave with lucky number
// shortestPathWithoutLuckyNumber[j] = Shortest path from A / B to 1 known that sum of exp = j
vector <int> shortestPathWithoutLuckyNumber(MAX_SUM_EXP + 2, 0); // base2
for (int sumOfExp = 1; sumOfExp <= sumExponent[compressSource]; sumOfExp++)
shortestPathWithoutLuckyNumber[sumOfExp] = shortestPathTo1[compressSource][sumOfExp];
// shortestPathLuckyNumber[j] = Shortest path from A to B known that sum of exp = j using lucky number
vector <int> shortestPathLuckyNumber(numQueriesLuckyNumber + 1, INF); // base3
// canUseCost: The array list all cost can use for optimization path
vector <int> canUseCost;
for (int indexOfLuckyNumber = 0; indexOfLuckyNumber < numQueriesLuckyNumber; indexOfLuckyNumber++) {
// The other way is using one lucky number for immediate point
// A --> X --> B, X is lucky number
if ((firstNumber % listLuckyNumber[indexOfLuckyNumber] != 0) || (listLuckyNumber[indexOfLuckyNumber] % secondNumber != 0))
continue;
int compressAX = firstNumber / listLuckyNumber[indexOfLuckyNumber];
int compressBX = listLuckyNumber[indexOfLuckyNumber] / secondNumber;
// shortestPathImmediate[j] = Shortest path from A to B known that sum of exp = j and must through lucky number
vector <int> shortestPathImmediate(MAX_SUM_EXP + 2, INF); // base1
for (int sumOfExpAX = 0; sumOfExpAX <= sumExponent[compressAX]; sumOfExpAX++) {
for (int sumOfExpBX = 0; sumOfExpBX <= sumExponent[compressBX]; sumOfExpBX++) {
shortestPathImmediate[sumOfExpAX + sumOfExpBX]
= min(shortestPathImmediate[sumOfExpAX + sumOfExpBX],
shortestPathTo1[compressAX][sumOfExpAX] + shortestPathTo1[compressBX][sumOfExpBX]);
}
}
shortestPathLuckyNumber[indexOfLuckyNumber] = INF;
for (int sumOfExp = 0; sumOfExp <= sumExponent[compressSource]; sumOfExp++) {
shortestPathLuckyNumber[indexOfLuckyNumber]
= min(shortestPathLuckyNumber[indexOfLuckyNumber] + listCostLuckyNumber[indexOfLuckyNumber],
shortestPathImmediate[sumOfExp]);
shortestPathWithoutLuckyNumber[sumOfExp]
= min(shortestPathWithoutLuckyNumber[sumOfExp], shortestPathLuckyNumber[indexOfLuckyNumber]);
}
if (shortestPathLuckyNumber[indexOfLuckyNumber] != INF)
canUseCost.push_back(indexOfLuckyNumber);
}
long long res = 0;
for (int indexOfLength = 0; indexOfLength < numQueriesLength; indexOfLength++) {
if (listLength[indexOfLength] <= sumExponent[compressSource]) {
if (shortestPathWithoutLuckyNumber[listLength[indexOfLength]] == INF)
res -= 1;
else
res += shortestPathWithoutLuckyNumber[listLength[indexOfLength]];
}
else {
int cur = INF;
for (auto &id: canUseCost) {
// Let's go over all possible lucky number and look at the formula
// for the total number of moves L, and denote with L' the number of moves
// when we leave C on the board:
cur = min(cur, (listLength[indexOfLength] - sumExponent[compressSource]) * listCostLuckyNumber[id] + shortestPathLuckyNumber[id]);
}
if (cur == INF)
res += -1;
else
res += cur;
}
}
cout << res << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1329 ms |
125696 KB |
Output is correct |
| 2 |
Correct |
1335 ms |
125700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1278 ms |
125708 KB |
Output is correct |
| 2 |
Correct |
1331 ms |
125700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1338 ms |
125780 KB |
Output is correct |
| 2 |
Correct |
1312 ms |
125712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1347 ms |
125708 KB |
Output is correct |
| 2 |
Correct |
1395 ms |
125744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1427 ms |
126500 KB |
Output is correct |
| 2 |
Correct |
1467 ms |
126484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1449 ms |
126484 KB |
Output is correct |
| 2 |
Correct |
1491 ms |
126548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1436 ms |
126660 KB |
Output is correct |
| 2 |
Correct |
1684 ms |
126664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1574 ms |
126868 KB |
Output is correct |
| 2 |
Correct |
1390 ms |
126568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1568 ms |
126584 KB |
Output is correct |
| 2 |
Correct |
1413 ms |
126588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1580 ms |
126488 KB |
Output is correct |
| 2 |
Correct |
1501 ms |
126484 KB |
Output is correct |
