oj.uz

Submission #90480

# Submission time Handle Problem Language Result Execution time Memory
90480 2018-12-21T20:23:17 Z radoslav11 Brunhilda’s Birthday (BOI13_brunhilda) C++14
81.746 / 100
 459 ms 89492 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)1e7 + 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 116 ms 78584 KB Output is correct
2 Correct 154 ms 78844 KB Output is correct
3 Correct 127 ms 78872 KB Output is correct
4 Correct 111 ms 78872 KB Output is correct
5 Correct 144 ms 78940 KB Output is correct
6 Correct 111 ms 78940 KB Output is correct
7 Correct 134 ms 78940 KB Output is correct
8 Correct 128 ms 78940 KB Output is correct
9 Correct 167 ms 78940 KB Output is correct
10 Correct 186 ms 78940 KB Output is correct
11 Correct 181 ms 78940 KB Output is correct
12 Correct 108 ms 78940 KB Output is correct
13 Correct 320 ms 78940 KB Output is correct
14 Correct 298 ms 78940 KB Output is correct
15 Correct 139 ms 79092 KB Output is correct
16 Correct 145 ms 79092 KB Output is correct
17 Correct 159 ms 79092 KB Output is correct
18 Correct 115 ms 79188 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 79188 KB Output is correct
2 Correct 138 ms 79264 KB Output is correct
3 Correct 415 ms 79264 KB Output is correct
4 Correct 175 ms 79264 KB Output is correct
5 Correct 280 ms 79264 KB Output is correct
6 Correct 144 ms 79264 KB Output is correct
7 Correct 141 ms 79264 KB Output is correct
8 Correct 175 ms 79264 KB Output is correct
9 Correct 329 ms 79264 KB Output is correct
10 Correct 417 ms 79360 KB Output is correct
11 Incorrect 410 ms 79360 KB Output isn't correct
12 Correct 222 ms 79360 KB Output is correct
13 Correct 118 ms 79360 KB Output is correct
14 Correct 174 ms 79360 KB Output is correct
15 Correct 329 ms 79360 KB Output is correct
16 Correct 124 ms 79360 KB Output is correct
17 Correct 286 ms 79360 KB Output is correct
18 Correct 327 ms 79360 KB Output is correct

Subtask #3
42.8571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 79420 KB Output is correct
2 Correct 349 ms 79444 KB Output is correct
3 Correct 371 ms 79768 KB Output is correct
4 Incorrect 217 ms 80276 KB Output isn't correct
5 Incorrect 173 ms 80604 KB Output isn't correct
6 Correct 321 ms 80960 KB Output is correct
7 Correct 313 ms 81128 KB Output is correct
8 Correct 340 ms 81128 KB Output is correct
9 Correct 315 ms 81128 KB Output is correct
10 Correct 226 ms 81128 KB Output is correct
11 Incorrect 206 ms 81128 KB Output isn't correct
12 Correct 262 ms 81128 KB Output is correct
13 Correct 329 ms 81936 KB Output is correct
14 Correct 194 ms 82864 KB Output is correct
15 Incorrect 272 ms 82864 KB Output isn't correct
16 Correct 328 ms 82864 KB Output is correct
17 Correct 336 ms 82864 KB Output is correct
18 Correct 432 ms 82864 KB Output is correct
19 Incorrect 137 ms 82864 KB Output isn't correct
20 Correct 418 ms 83100 KB Output is correct
21 Incorrect 255 ms 84104 KB Output isn't correct
22 Correct 415 ms 84708 KB Output is correct
23 Correct 191 ms 84708 KB Output is correct
24 Correct 160 ms 84708 KB Output is correct
25 Correct 296 ms 85064 KB Output is correct
26 Incorrect 269 ms 85596 KB Output isn't correct
27 Correct 459 ms 86056 KB Output is correct
28 Incorrect 151 ms 86056 KB Output isn't correct
29 Correct 426 ms 86776 KB Output is correct
30 Correct 372 ms 87288 KB Output is correct
31 Correct 196 ms 87288 KB Output is correct
32 Incorrect 212 ms 87288 KB Output isn't correct
33 Incorrect 141 ms 87288 KB Output isn't correct
34 Correct 304 ms 87288 KB Output is correct
35 Incorrect 161 ms 87288 KB Output isn't correct
36 Correct 399 ms 87916 KB Output is correct
37 Incorrect 155 ms 87916 KB Output isn't correct
38 Correct 326 ms 88188 KB Output is correct
39 Correct 168 ms 88188 KB Output is correct
40 Correct 298 ms 88712 KB Output is correct
41 Correct 250 ms 88980 KB Output is correct
42 Correct 377 ms 89492 KB Output is correct