Submission #385980

#	Time	Username	Problem	Language	Result	Execution time	Memory
385980		blue	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	634 ms	81404 KiB

brunhilda

#include <iostream>
#include <vector>
#include <set>
#include <deque>
using namespace std;

const int lim = 1e7;

vector<int> res(lim+1, 1e9);
vector<int> factor(lim+1, 0);

int main()
{
    int M, Q;
    cin >> M >> Q;

    int p[M];
    for(int i = 0; i < M; i++)
    {
        cin >> p[i];
        for(int q = 0; q <= lim; q += p[i]) factor[q] = max(factor[q], p[i]);
    }

    deque<int> pos, val;
    pos.push_back(0);
    val.push_back(0);

    for(int i = 0; i <= lim; i++)
    {
        while(!pos.empty() && pos.front() < i)
        {
            pos.pop_front();
            val.pop_front();
        }

        if(pos.empty()) break;

        res[i] = val.front();

        if(pos.back() < i + factor[i] - 1)
        {
            pos.push_back(i + factor[i] - 1);
            val.push_back(res[i] + 1);
        }
    }

    while(Q--)
    {
        int q;
        cin >> q;
        if(res[q] == 1e9) cout << "oo\n";
        else cout << res[q] << '\n';
    }

}

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