Submission #140239

#	Time	Username	Problem	Language	Result	Execution time	Memory
140239		Minnakhmetov	Gauss (COCI17_gauss)	C++14	32 / 160	2082 ms	137440 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 = 289, M = 100, INF = 1e9;
int f[N], len[N], state[N], gg[N], ww[N], sum[Z],
    divisor[N], primes[10], dp[Z][M][Z][2], 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 < 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();
 
    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 < 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);
    }

    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]);
            }
        }
 
        cht.cl();
 
        for (int j = 0; j < t; j++) {
            if (lucky[j].second % b == 0 && a % lucky[j].second == 0) {
                int x = state[lucky[j].second / b], mn = INF;

                for (int k = 0; k < M; k++) {
                    if (dp[x][k][d][1] != INF) {
                        for (int h = k; h < M; h++) {
                            upd(small_ans[h], dp[x][k][d][1] + lucky[j].first * (h - k));
                        }
                        upd(mn, dp[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) {
                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:124:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (pos + 1 < size() && (begin() + pos + 1)->lx <= x)
                ~~~~~~~~^~~~~~~~

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