oj.uz

Submission #243439

# Submission time Handle Problem Language Result Execution time Memory
243439 2020-07-01T07:29:20 Z anubhavdhar Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 506 ms 1152 KB 
#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()

using namespace std;

const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 1e4+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const int inf = 1e9 + 4;

int dp[MAXN], m, Q, p[MAXN];

inline void init()
{
	cin>>m>>Q;
	F0R(i, m)
		cin>>p[i];
	sort(p, p + m);
	dp[0] = inf;
	dp[1] = 1;
	F0Rr(i, 2, MAXN)
	{
		dp[i] = inf;
		F0R(j, m)
			if(i%p[j] != 0)
				dp[i] = min(dp[i], ((p[j] > i) ? 1 : (1 + dp[i - i%p[j]])));
	}
	// dbgLine;
}

int main()
{
	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/
	int n;
	init();
	F0R(i, Q)
	{
		cin>>n;
		if(dp[n] < inf)
			cout<<dp[n]<<'\n';
		else
			cout<<"oo\n";
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 6 ms 432 KB Output is correct
4 Correct 32 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 9 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 10 ms 512 KB Output is correct
13 Correct 61 ms 384 KB Output is correct
14 Correct 81 ms 384 KB Output is correct
15 Correct 8 ms 384 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 31 ms 384 KB Output is correct
18 Correct 34 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 171 ms 672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 69 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 15 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 59 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 15 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 118 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 160 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 173 ms 608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 167 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 14 ms 1056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 187 ms 736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 442 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 321 ms 864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 241 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 321 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 7 ms 556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 300 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 385 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 283 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 15 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 11 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 66 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 161 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 188 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 59 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 14 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 240 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 161 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 71 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 15 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 112 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 440 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 128 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 506 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 14 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 167 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)