oj.uz

Submission #90485

# Submission time Handle Problem Language Result Execution time Memory
90485 2018-12-21T20:32:44 Z radoslav11 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 914 ms 157880 KB 
/*
	There is a simple solution with upper bound on the time equal to O(MAX * log(log(MAX)) * log(MAX)) with DP and maintaining a heap. Probably the actual complexity is smaller.
	Unfortunately this was too slow, but we can notice that there is monotonicity in the answers and so if at each step we remove the largest number of people we will have an optimal strategy.
	This also means we can remove the heap from the dp and just find the largest transition.
*/
 
#include <bits/stdc++.h>
#define endl '\n'
 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
 
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
 
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int B = (int)2e7 + 42;
const int inf = B + 42;
 
int n, q;
int dp[B + 42];
int a[MAXN], trans[B + 42];
 
void read()
{
	cin >> n >> q;
	for(int i = 0; i < n; i++)
		cin >> a[i];
}
 
void solve()
{
	for(int i = 0; i < a[n - 1]; i++) dp[i] = 1;
	for(int i = a[n - 1]; i <= B; i++) dp[i] = inf;
 
	for(int i = 0; i < n; i++)
		for(int j = a[i] - 1; j <= B; j += a[i])
			trans[j] = a[i] - 1;
 
	for(int i = B; i >= 0; i--)
		chkmax(trans[i], trans[i + 1] - 1);
 
	for(int d = a[n - 1]; d <= B; d++)
		chkmin(dp[d], 1 + dp[d - trans[d]]);
 
	while(q--)
	{
		int x;
		cin >> x;
		if(dp[x] == inf) cout << "oo" << endl;
		else cout << dp[x] << endl;
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	read();
	solve();
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 156924 KB Output is correct
2 Correct 305 ms 157148 KB Output is correct
3 Correct 257 ms 157148 KB Output is correct
4 Correct 231 ms 157148 KB Output is correct
5 Correct 268 ms 157148 KB Output is correct
6 Correct 187 ms 157212 KB Output is correct
7 Correct 218 ms 157212 KB Output is correct
8 Correct 279 ms 157228 KB Output is correct
9 Correct 310 ms 157228 KB Output is correct
10 Correct 396 ms 157228 KB Output is correct
11 Correct 347 ms 157228 KB Output is correct
12 Correct 219 ms 157228 KB Output is correct
13 Correct 583 ms 157304 KB Output is correct
14 Correct 574 ms 157304 KB Output is correct
15 Correct 269 ms 157304 KB Output is correct
16 Correct 251 ms 157304 KB Output is correct
17 Correct 265 ms 157304 KB Output is correct
18 Correct 195 ms 157304 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 157304 KB Output is correct
2 Correct 244 ms 157564 KB Output is correct
3 Correct 705 ms 157608 KB Output is correct
4 Correct 303 ms 157608 KB Output is correct
5 Correct 477 ms 157608 KB Output is correct
6 Correct 265 ms 157608 KB Output is correct
7 Correct 242 ms 157608 KB Output is correct
8 Correct 299 ms 157608 KB Output is correct
9 Correct 567 ms 157608 KB Output is correct
10 Correct 697 ms 157608 KB Output is correct
11 Correct 700 ms 157608 KB Output is correct
12 Correct 405 ms 157608 KB Output is correct
13 Correct 221 ms 157608 KB Output is correct
14 Correct 333 ms 157608 KB Output is correct
15 Correct 582 ms 157608 KB Output is correct
16 Correct 299 ms 157608 KB Output is correct
17 Correct 714 ms 157608 KB Output is correct
18 Correct 644 ms 157608 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 157608 KB Output is correct
2 Correct 851 ms 157608 KB Output is correct
3 Correct 856 ms 157608 KB Output is correct
4 Correct 482 ms 157608 KB Output is correct
5 Correct 338 ms 157848 KB Output is correct
6 Correct 673 ms 157848 KB Output is correct
7 Correct 601 ms 157848 KB Output is correct
8 Correct 672 ms 157848 KB Output is correct
9 Correct 642 ms 157848 KB Output is correct
10 Correct 565 ms 157848 KB Output is correct
11 Correct 474 ms 157848 KB Output is correct
12 Correct 591 ms 157848 KB Output is correct
13 Correct 791 ms 157848 KB Output is correct
14 Correct 434 ms 157848 KB Output is correct
15 Correct 644 ms 157848 KB Output is correct
16 Correct 746 ms 157848 KB Output is correct
17 Correct 658 ms 157848 KB Output is correct
18 Correct 851 ms 157848 KB Output is correct
19 Correct 260 ms 157848 KB Output is correct
20 Correct 873 ms 157848 KB Output is correct
21 Correct 506 ms 157880 KB Output is correct
22 Correct 865 ms 157880 KB Output is correct
23 Correct 360 ms 157880 KB Output is correct
24 Correct 309 ms 157880 KB Output is correct
25 Correct 545 ms 157880 KB Output is correct
26 Correct 478 ms 157880 KB Output is correct
27 Correct 914 ms 157880 KB Output is correct
28 Correct 281 ms 157880 KB Output is correct
29 Correct 810 ms 157880 KB Output is correct
30 Correct 760 ms 157880 KB Output is correct
31 Correct 344 ms 157880 KB Output is correct
32 Correct 385 ms 157880 KB Output is correct
33 Correct 260 ms 157880 KB Output is correct
34 Correct 568 ms 157880 KB Output is correct
35 Correct 333 ms 157880 KB Output is correct
36 Correct 803 ms 157880 KB Output is correct
37 Correct 348 ms 157880 KB Output is correct
38 Correct 663 ms 157880 KB Output is correct
39 Correct 321 ms 157880 KB Output is correct
40 Correct 586 ms 157880 KB Output is correct
41 Correct 493 ms 157880 KB Output is correct
42 Correct 763 ms 157880 KB Output is correct