Submission #140205

#	Time	Username	Problem	Language	Result	Execution time	Memory
140205		Minnakhmetov	Gauss (COCI17_gauss)	C++14	0 / 160	716 ms	85980 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], lucky[L], price[L], 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];
map<vector<int>, int> mp;
vector<int> vec[N], st_vec[Z];
int pr_cnt = 0;
vector<int> cur;

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

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

    cin >> t;

    for (int i = 0; i < t; i++) {
        cin >> lucky[i] >> price[i];
    }

    cin >> q;

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

        for (int j = 0; j < t; j++) {
            if (lucky[j] % b == 0 && a % lucky[j] == 0) {
                int x = lucky[j] / b;
                for (int k = 0; k < M; k++) {
                    for (int h = k; h < M; h++) {
                        upd(small_ans[h], dp[state[x]][k][d][1] + price[j] * (h - k));
                    }
                }
            }
        }

        ll ans = 0;
        for (int j = 0; j < m; j++) {
            if (len[j] >= M)
                return 1;
            ans += (small_ans[len[j]] == INF ? -1 : small_ans[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:21: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:56:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x == v.size()) {
         ~~^~~~~~~~~~~
gauss.cpp:83:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
gauss.cpp: In function 'int main()':
gauss.cpp:93:13: warning: unused variable 'start' [-Wunused-variable]
     clock_t start = clock();
             ^~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 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