Submission #140221

#TimeUsernameProblemLanguageResultExecution timeMemory
140221MinnakhmetovGauss (COCI17_gauss)C++14
0 / 160
2093 ms86776 KiB
#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], 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); 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); } if (mn != INF) cht.addLine({ lucky[j].first, mn }); } } 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 (stderr)

gauss.cpp: In function 'int getId(const std::vector<int>&)':
gauss.cpp:22: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:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x == v.size()) {
         ~~^~~~~~~~~~~
gauss.cpp:84:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
gauss.cpp: In member function 'int CHT::que(int)':
gauss.cpp:134: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:154:13: warning: unused variable 'start' [-Wunused-variable]
     clock_t start = clock();
             ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...