Submission #546536

#	Time	Username	Problem	Language	Result	Execution time	Memory
546536		_martynas	Brunhilda’s Birthday (BOI13_brunhilda)	C++11	100 / 100	280 ms	127120 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define F first
#define S second

using pii = pair<int, int>;

const int MXN = 1e5+5;
const int MXM = 1e7+5;
const int INF = 1e8;

int m, q;
int P[MXN];
int dp[MXM];
int add[MXM];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> m >> q;

    for(int i = 0; i < m; i++) {
        cin >> P[i];
    }

    fill(dp, dp + MXM, INF);

    for(int i = 0; i < m; i++) {
        // prime can exceed maximum!
        // only the place which transition leads to needs to fit
        for(int p = P[i]; p - P[i] < MXM; p += P[i]) {
            add[p - P[i]] = P[i];
        }
    }

    dp[0] = 0;
    queue<pii> Q;
    for(int i = 0; i < MXM; i++) {
        while(!Q.empty() && Q.front().F + Q.front().S <= i) {
            Q.pop();
        }

        if(!Q.empty()) {
            dp[i] = min(INF, dp[Q.front().S]+1);
        }

        if(add[i]) {
            Q.push({add[i], i});
        }
    }

    for(int qq = 0; qq < q; qq++) {
        int n;
        cin >> n;
        if(dp[n] >= INF) {
            cout << "oo\n";
        }
        else {
            cout << dp[n] << "\n";
        }
    }

    return 0;
}
/*
2 2
2 3
5
6
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60