Submission #140228

#	Time	Username	Problem	Language	Result	Execution time	Memory
140228		Minnakhmetov	Gauss (COCI17_gauss)	C++14	32 / 160	2068 ms	86864 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 = 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);
    reverse(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);
                }
                // cout << lucky[j].first << " " << mn << "\n";
                if (mn != INF)
                    cht.addLine({ lucky[j].first, mn });
            }
        }

        // for (Line a : cht) {
        //     cout << a.k << " " << a.b << " " << a.lx << "\n";
        // }

        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();
             ^~~~~

• 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