Submission #155750

#	Time	Username	Problem	Language	Result	Execution time	Memory
155750		souhhcong	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	78.10 / 100	801 ms	79504 KiB

brunhilda

#include <iostream>
#include <string.h>
using namespace std;

const int N = 1e5+5, MAXN = 1e7+7, INF = 1e9+9;
int n, q, x, p[N], dp[MAXN], mx[MAXN];

int main()
{
    cin >> n >> q;
    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        for (int j = p[i]-1; j < MAXN; j += p[i])
        {
            mx[j] = max(mx[j], p[i]-1);
        }
    }
	for (int i = MAXN - 2; i >= 0; i--)
		mx[i] = max(mx[i], mx[i+1]-1);
    for (int i = 1; i < MAXN; i++)
    {
        if (mx[i] > 0)
            dp[i] = 1 + dp[i-mx[i]];
        else
            dp[i] = INF;
    }
    while(q--)
    {
        cin >> x;
        if (dp[x] == INF) cout << "oo\n";
        else cout << dp[x] << '\n';
    }
}

• Subtask 1: 17.77777777777778 / 20
• Subtask 2: 18.88888888888889 / 20
• Subtask 3: 41.42857142857143 / 60