Submission #140277

#	Time	Username	Problem	Language	Result	Execution time	Memory
140277		Minnakhmetov	Gauss (COCI17_gauss)	C++14	160 / 160	541 ms	72600 KiB

gauss

#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 = 300, M = 21, INF = 1e9;
int f[N], len[N], state[N], gg[N], ww[N], sum[Z],
    divisor[N], primes[10], dp[M][Z], small_ans[M], 
    trie[Z][M], num[Z];

int pr_cnt = 0, cv = 1, cnt = 0;
 
pair<int, int> lucky[L];
vector<int> vec[N], st_vec[Z], cur; 
 
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) {
    num[v] = cnt;
    sum[cnt] = s;
    st_vec[cnt] = cur;
    cnt++;
 
    cur.push_back(1);
    prod *= primes[x];
    while (prod < N && cur[x] <= last) {
        trie[v][cur[x]] = cv++;
        rec(x + 1, cur[x], prod, s + cur[x], trie[v][cur[x]]);
        cur[x]++;
        prod *= primes[x];
    }
    cur.pop_back();
}
 
void upd(int &a, int b) {
    a = min(a, b);
}
 
void 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 <= sum[from]; i++) {
                upd(dp[i + 1][to], dp[i][from] + 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();
 
    int n, m, t, q;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }
 
    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);


    // end of input reading


    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;
        }
    }

    // for (int i = 0; i < pr_cnt; i++) {
    //     cout << primes[i] << "\n";
    // }
 
    memset(num, -1, sizeof(num));
    memset(trie, -1, sizeof(trie));
 
    rec(0, INF, 1, 0, 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]);
    }

    for (int x = 0; x < M; x++) {
        for (int j = 0; j < Z; j++) {
            dp[x][j] = INF;
        }
    }

    dp[0][0] = 0;
    
    for (int i = 0; i < cnt; i++) {
        rec_dp(0, st_vec[i], 1, i);
    }


    cin >> q;
 
    CHT cht;
 
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;

        ll ans = 0;
 
        if (a % b) {
            ans = -m;
        }
        else {
            fill(small_ans, small_ans + M, INF);

            int d = state[a / b];

            for (int x = 0; x < M; x++) {
                upd(small_ans[x], dp[x][d]);
            }

            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, y = a / lucky[j].second, mn = INF;

                    x = state[x];
                    y = state[y];

                    for (int k = 0; k <= sum[x]; k++) {
                        for (int h = 0; h <= sum[y]; h++) {
                            if (dp[k][x] != INF && dp[h][y] != INF) {
                                for (int z = 0; z + k + h < M; z++) {
                                    upd(small_ans[k + h + z], dp[k][x] + dp[h][y] + lucky[j].first * z);
                                }
                                upd(mn, dp[k][x] + dp[h][y] - lucky[j].first * (k + h));
                            }
                        }
                    }

                    if (mn != INF)
                        cht.addLine({ lucky[j].first, mn });
                }
            }

            for (int j = 0; j < m; j++) {
                if (len[j] < M) {
                    if (small_ans[len[j]] == INF)
                        ans--;
                    else
                        ans += 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:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); i++) {
                     ~~^~~~~~~~~~
gauss.cpp: In function 'void rec_dp(int, std::vector<int>&, int, int)':
gauss.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x == v.size()) {
         ~~^~~~~~~~~~~
gauss.cpp: In member function 'int CHT::que(int)':
gauss.cpp:121:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pos + 1 < size() && (begin() + pos + 1)->lx <= x)
                ~~~~~~~~^~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16