제출 #256236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256236		shayan_p	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	20 / 100	42 ms	12652 KiB

brunhilda

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, MAX = 1e4 + 10, mod = 1e9 + 7, inf = 1e9 + 10; //////

int a[maxn], dp[MAX];
set<pii> st;
priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> vec;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n, q;
    cin >> n >> q;
    int lm = 1;
    for(int i = 0; i < n; i++){
	cin >> a[i];
        lm = min(1ll * lm * a[i], ll(MAX));
	pq.push({0, a[i]});
	st.insert({1, a[i]});
    }
    for(int i = 0; i < lm; i++){
	vec.clear();
	while(!pq.empty() && pq.top().F == i){
	    int p = pq.top().S;
	    vec.PB(p);
	    pq.pop();
	    st.erase({dp[i-p] + 1, p});
	}
	if(i > 0)
	    assert(sz(st)), dp[i] = st.begin()->F;
	for(int x : vec){
	    st.insert({dp[i] + 1, x});
	    pq.push({i + x, x});
	}
    }
    while(q--){
	int x;
	cin >> x;
	if(x >= lm)
	    cout << "oo\n";
	else
	    cout << dp[x] << "\n";
    }
    return 0;
}

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