Submission #1142993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142993		Rainmaker2627	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	0 / 100	1105 ms	302372 KiB

brunhilda

#include<bits/stdc++.h>
using namespace std;

struct lpq {
    priority_queue<int> a, b;
    void push(int x) { a.push(-x); }
    void pop(int x) { b.push(-x); }
    int top() {
        while (!b.empty() && a.top()==b.top()) {
            a.pop(); b.pop();
        } return (a.empty()?-2:-a.top());
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n=1e7, m, q;
    cin >> m >> q;
    vector<int> pr(m);
    for (int i = 0; i < m; i++) {
        cin >> pr[i];
    }
    
    lpq pq;
    priority_queue<pair<int, int>> sv;
    vector<int> dp(n+1, -1);
    for (int i = 0; i < m; i++) {
        sv.push({-pr[i], pr[i]}); pq.push(0);
    }

    dp[0]=0;
    for (int i = 1; i <= n; i++) {
        int c=0;
        while (-sv.top().first==i) {
            auto [a, b]=sv.top();
            sv.push({-a-b, b});
            pq.pop(dp[i-b]);
            sv.pop();
            c++;
        } dp[i]=pq.top()+1;
        if (dp[i]==-1) continue;
        while (c--) pq.push(dp[i]);
    }
    
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        if (dp[x]==-1) cout << "oo\n";
        else cout << dp[x] << '\n';
    }

    return 0;
}

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