제출 #256255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256255		Saboon	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	46.98 / 100	809 ms	262148 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
 
const int maxn = 1e7 + 10;

int cnt[maxn];
int last[maxn], pre[6*maxn], p[6*maxn];
int Q[6*maxn], tail, head;
int dp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int m, q;
	cin >> m >> q;
	int sz = 0;
	memset(last, -1, sizeof last);
	for (int i = 0; i < m; i++){
		int x;
		cin >> x;
		p[sz] = x, pre[sz] = last[0], last[0] = sz ++;
	}
	int n = 1000*1000*10;
	int mxm = n+1;
	for (int i = 0; i <= n; i++){
		while (last[i] != -1){
			int idx = last[i];
			if (i > 0)
				cnt[i-p[idx]] ++;
			Q[head++] = i;
			if (i+p[idx] <= n)
				p[sz] = p[idx], pre[sz] = last[i+p[idx]], last[i+p[idx]] = sz ++;
			last[i] = pre[last[i]];
		}
		while (tail < head and cnt[Q[tail]] > 0)
			cnt[Q[tail++]] --;
		if (i > 0){
			if (Q[tail] == i){
				dp[i] = -1;
				mxm = i;
				break;
			}
			dp[i] = dp[Q[tail]] + 1;
		}
	}
	while (q --){
		int x;
		cin >> x;
		if (x >= mxm)
			cout << "oo\n";
		else
			cout << dp[x] << '\n';
	}
}

• Subtask 1: 15.555555555555555 / 20
• Subtask 2: 10 / 20
• Subtask 3: 21.428571428571427 / 60