| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 249381 |
2020-07-14T19:21:12 Z |
VEGAnn |
Gauss (COCI17_gauss) |
C++14 |
|
352 ms |
17144 KB |
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
using namespace std;
typedef long long ll;
const int PW = 22;
const int K = 10010;
const int M = 1010;
const int T = 55;
const int BIG = 1000100;
const int oo = int(3e4);
const int ooi = 2e9;
const int CN = 300;
vector<i2> elms;
vector<int> vc;
int k, F[K], L[M], X[T], C[T], cnt = 0, pri[7] = {2, 3, 5, 7, 11, 13, 17};
int mn[BIG], decomp[BIG], m, t, inv[CN];
short ind[BIG], ans[CN][CN][T][PW], f[CN][PW], dp[CN][CN][PW];
void amin(int &x, int y){
x = min(x, y);
}
void amin_sh(short &x, short y){
x = min(x, y);
}
struct CHT{
vector<i2> cht;
vector<int> fr;
};
CHT hull;
int divide(int K, int B){
if ((K < 0 && B < 0) || (K > 0 && B > 0))
return (B / K) + bool(B % K != 0);
else return (B / K);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
fill(mn, mn + BIG, ooi);
for (int i = 2; i < BIG; i++){
if (mn[i] < ooi) continue;
mn[i] = i;
if (ll(i) * ll(i) >= ll(BIG)) continue;
for (int j = i * i; j < BIG; j += i)
mn[j] = min(mn[j], i);
}
for (int i = 1; i < BIG; i++){
vc.clear();
int xx = i;
while (xx > 1){
int cur = mn[xx], kol = 0;
while (xx % cur == 0){
kol++;
xx /= cur;
}
vc.PB(kol);
}
sort(all(vc));
reverse(all(vc));
for (int it = 0; it < sz(vc); it++)
for (int cr = 0; cr < vc[it]; cr++)
xx *= pri[it];
decomp[i] = xx;
if (xx == i) {
inv[cnt] = i;
ind[i] = cnt++;
}
}
cin >> k;
for (int i = 1; i <= k; i++)
cin >> F[i];
cin >> m;
for (int i = 0; i < m; i++)
cin >> L[i];
sort(L, L + m);
cin >> t;
for (int i = 0; i < t; i++)
cin >> X[i] >> C[i];
for (int i = 0; i < cnt; i++){
fill(f[i], f[i] + PW, oo);
if (i == 0){
f[i][0] = 0;
continue;
}
for (int pr = 0; pr < i; pr++)
if (inv[i] % inv[pr] == 0){
int val = 1, xx = (inv[i] / inv[pr]);
while (xx > 1){
int kol = 0, cur = mn[xx];
while (xx % cur == 0){
kol++;
xx /= cur;
}
val *= (kol + 1);
}
for (int len = 0; len < PW; len++)
if (f[pr][len] < oo)
amin_sh(f[i][len + 1], f[pr][len] + F[val]);
}
}
for (int i = 0; i < cnt; i++)
for (int j = i; j < cnt; j++){
if (ll(inv[i]) * ll(inv[j]) >= BIG) continue;
fill(dp[i][j], dp[i][j] + PW, oo);
for (int p1 = 0; p1 < PW; p1++){
if (f[i][p1] == oo) continue;
for (int p2 = 0; p2 < PW; p2++)
if (f[j][p2] < oo)
amin_sh(dp[i][j][p1 + p2], f[i][p1] + f[j][p2]);
}
for (int tp = 0; tp < t; tp++){
fill(ans[i][j][tp], ans[i][j][tp] + PW, oo);
for (int len = 0; len < PW; len++) {
if (dp[i][j][len] == oo) continue;
int cur = dp[i][j][len];
for (int ad = 0; ad + len < PW; ad++){
if (ad > 0)
cur += C[tp];
amin_sh(ans[i][j][tp][ad + len], cur);
}
}
}
}
int qq; cin >> qq;
for (; qq; qq--){
int A, B; cin >> A >> B;
if (A % B != 0){
cout << -m << '\n';
continue;
}
elms.clear();
for (int tp = 0; tp < t; tp++)
if (A % X[tp] == 0 && X[tp] % B == 0){
int best = ooi;
int b1 = ind[decomp[A / X[tp]]];
int b2 = ind[decomp[X[tp] / B]];
if (b1 > b2) swap(b1, b2);
for (int len = 0; len < PW; len++)
if (dp[b1][b2][len] < oo)
amin(best, dp[b1][b2][len] - len * C[tp]);
elms.PB({-C[tp], best});
}
sort(all(elms));
if (sz(elms) > 0){
hull.fr.clear();
hull.cht.clear();
hull.fr.PB(-ooi);
hull.cht.PB({elms[0][0] * -1, elms[0][1]});
for (int i = 1; i < sz(elms); i++){
if (elms[i][0] == elms[i - 1][0]) continue;
i2 cur = elms[i];
cur[0] *= -1;
while (sz(hull.cht) > 1){
int pos = divide(cur[0] - hull.cht.back()[0], hull.cht.back()[1] - cur[1]);
if (pos > hull.fr.back()) break;
hull.cht.pop_back();
hull.fr.pop_back();
}
hull.fr.PB(divide(cur[0] - hull.cht.back()[0], hull.cht.back()[1] - cur[1]));
hull.cht.PB(cur);
}
}
int base = ind[decomp[A / B]], ptr = 0;
ll res = 0;
for (int i = 0; i < m; i++)
if (L[i] < PW) {
int cur = ooi;
if (f[base][L[i]] < oo)
amin(cur, f[base][L[i]]);
for (int tp = 0; tp < t; tp++)
if (A % X[tp] == 0 && X[tp] % B == 0){
int b1 = ind[decomp[A / X[tp]]];
int b2 = ind[decomp[X[tp] / B]];
if (b1 > b2) swap(b1, b2);
if (ans[b1][b2][tp][L[i]] < oo)
amin(cur, ans[b1][b2][tp][L[i]]);
}
if (cur < ooi)
res += cur;
else res--;
} else {
if (sz(elms) == 0)
res--;
else {
while (ptr + 1 < sz(hull.cht) && hull.fr[ptr + 1] <= L[i])
ptr++;
res += hull.cht[ptr][1] + hull.cht[ptr][0] * L[i];
}
}
cout << res << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
16248 KB |
Output is correct |
| 2 |
Correct |
144 ms |
16248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
16248 KB |
Output is correct |
| 2 |
Correct |
147 ms |
16248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
16248 KB |
Output is correct |
| 2 |
Correct |
144 ms |
16248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
16232 KB |
Output is correct |
| 2 |
Correct |
143 ms |
16316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
17132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
17084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
211 ms |
17144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
262 ms |
17144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
352 ms |
17144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
331 ms |
17144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
