Submission #206913

# Submission time Handle Problem Language Result Execution time Memory
206913 2020-03-05T19:51:52 Z MvC Brunhilda’s Birthday (BOI13_brunhilda) C++11
100 / 100
389 ms 119544 KB
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e7+50;
const int mod=1e9+7;
using namespace std;
int n,q,f[nmax],mx[2*nmax],x,i,j;
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		for(j=0;j<=1e7;j+=x)mx[j+x-1]=max(mx[j+x-1],x-1);
	}
	for(i=2e7;i>=1;i--)mx[i]=max(mx[i],mx[i+1]-1);
	for(i=1;i<=1e7;i++)
	{
		f[i]=inf;
		f[i]=f[i-mx[i]]+1;
	}
	while(q--)
	{
		cin>>x;
		if(f[x]>=inf)cout<<"oo\n";
		else cout<<f[x]<<'\n';
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 128 ms 117752 KB Output is correct
2 Correct 155 ms 117752 KB Output is correct
3 Correct 145 ms 117752 KB Output is correct
4 Correct 136 ms 117752 KB Output is correct
5 Correct 140 ms 117752 KB Output is correct
6 Correct 129 ms 117752 KB Output is correct
7 Correct 146 ms 117788 KB Output is correct
8 Correct 146 ms 117740 KB Output is correct
9 Correct 164 ms 117752 KB Output is correct
10 Correct 187 ms 117808 KB Output is correct
11 Correct 172 ms 117752 KB Output is correct
12 Correct 128 ms 117752 KB Output is correct
13 Correct 291 ms 117752 KB Output is correct
14 Correct 283 ms 117880 KB Output is correct
15 Correct 163 ms 117752 KB Output is correct
16 Correct 155 ms 117752 KB Output is correct
17 Correct 154 ms 117880 KB Output is correct
18 Correct 126 ms 117756 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 147 ms 117880 KB Output is correct
2 Correct 162 ms 118392 KB Output is correct
3 Correct 340 ms 118264 KB Output is correct
4 Correct 174 ms 117752 KB Output is correct
5 Correct 251 ms 118072 KB Output is correct
6 Correct 150 ms 117752 KB Output is correct
7 Correct 146 ms 117884 KB Output is correct
8 Correct 172 ms 117752 KB Output is correct
9 Correct 284 ms 118264 KB Output is correct
10 Correct 344 ms 118264 KB Output is correct
11 Correct 350 ms 118008 KB Output is correct
12 Correct 206 ms 117752 KB Output is correct
13 Correct 135 ms 117752 KB Output is correct
14 Correct 168 ms 117752 KB Output is correct
15 Correct 283 ms 118136 KB Output is correct
16 Correct 162 ms 118392 KB Output is correct
17 Correct 283 ms 117880 KB Output is correct
18 Correct 292 ms 118520 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 307 ms 118520 KB Output is correct
2 Correct 359 ms 118296 KB Output is correct
3 Correct 374 ms 119032 KB Output is correct
4 Correct 241 ms 118648 KB Output is correct
5 Correct 200 ms 119544 KB Output is correct
6 Correct 317 ms 118776 KB Output is correct
7 Correct 277 ms 119032 KB Output is correct
8 Correct 300 ms 118648 KB Output is correct
9 Correct 304 ms 118520 KB Output is correct
10 Correct 246 ms 118008 KB Output is correct
11 Correct 208 ms 118012 KB Output is correct
12 Correct 269 ms 118008 KB Output is correct
13 Correct 353 ms 118904 KB Output is correct
14 Correct 217 ms 119032 KB Output is correct
15 Correct 283 ms 118196 KB Output is correct
16 Correct 312 ms 118136 KB Output is correct
17 Correct 286 ms 118136 KB Output is correct
18 Correct 360 ms 118520 KB Output is correct
19 Correct 147 ms 118008 KB Output is correct
20 Correct 355 ms 118660 KB Output is correct
21 Correct 242 ms 119288 KB Output is correct
22 Correct 380 ms 119544 KB Output is correct
23 Correct 199 ms 119032 KB Output is correct
24 Correct 168 ms 118864 KB Output is correct
25 Correct 259 ms 118820 KB Output is correct
26 Correct 241 ms 118776 KB Output is correct
27 Correct 389 ms 118876 KB Output is correct
28 Correct 164 ms 118776 KB Output is correct
29 Correct 360 ms 119288 KB Output is correct
30 Correct 323 ms 119420 KB Output is correct
31 Correct 187 ms 118648 KB Output is correct
32 Correct 206 ms 118852 KB Output is correct
33 Correct 153 ms 118776 KB Output is correct
34 Correct 292 ms 118520 KB Output is correct
35 Correct 171 ms 118392 KB Output is correct
36 Correct 359 ms 118904 KB Output is correct
37 Correct 200 ms 119416 KB Output is correct
38 Correct 305 ms 118904 KB Output is correct
39 Correct 177 ms 118776 KB Output is correct
40 Correct 271 ms 118904 KB Output is correct
41 Correct 250 ms 118520 KB Output is correct
42 Correct 333 ms 118140 KB Output is correct