Submission #47000

#	Time	Username	Problem	Language	Result	Execution time	Memory
47000		rsalesc	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	530 ms	211176 KiB

brunhilda

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

const int P = 1e7+10;
const int M = 1e5+10;

struct Node {
	int v;
	Node * nxt;
};

int mx;
Node * q[P];
int dp[P];

Node* add(Node * no, int x) {
	return new Node({x, no});
}

void clear(Node * no) {
	if(no == 0) return;
	clear(no->nxt);
	delete no;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int m, Q;
	cin >> m >> Q;

	for(int i = 0; i < m; i++) {
		int x;
		cin >> x;
		q[0] = add(q[0], x);
	}

	for(int i = 1; i < P; i++) dp[i] = 1e9+10;

	for(int i = 0; i < P; i++) {
		Node* cur = q[i];
		while(cur) {
			int p = cur->v;
			int nxt = i+p;
			int til = min(nxt, P);

			for(int j = max(mx, i+1); j < til; j++) {
				dp[j] = dp[i]+1;
			}

			mx = max(mx, nxt);

			// fast jump
			nxt = mx / p * p;
			if(nxt < P) q[nxt] = add(q[nxt], p);
			cur = cur->nxt;
		}
	}

	for(int i = 0; i < Q; i++) {
		int x;
		cin >> x;
		if(dp[x] > 1e9) cout << "oo" << endl;
		else cout << dp[x] << endl;
	}
}

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