fork(6) download
copy 
  1. // Musketeers
  2. // AC, O(n log(n))
  3. // by Errichto
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6.  
  7. const int nax = 1e6 + 5;
  8. const int inf = 1e9 + 5;
  9. int m[3];
  10. multiset<int> enemies;
  11.  
  12. void greedy(int atLeast, int extra, int & ans) {
  13. 	while(!enemies.empty()) {
  14. 		auto it = enemies.end();
  15. 		--it;
  16. 		if(*it < atLeast) break;
  17. 		enemies.erase(it);
  18. 		++ans;
  19. 		it = enemies.lower_bound(extra);
  20. 		if(it != enemies.begin()) {
  21. 			--it;
  22. 			enemies.erase(it);
  23. 		}
  24. 	}
  25. }
  26.  
  27. int main() {
  28. 	int n;
  29. 	scanf("%d", &n);
  30. 	for(int i = 0; i < 3; ++i) scanf("%d", &m[i]);
  31. 	sort(m, m + 3);
  32. 	for(int i = 0; i < n; ++i) {
  33. 		int x;
  34. 		scanf("%d", &x);
  35. 		--x;
  36. 		enemies.insert(x);
  37. 	}
  38. 	int all = m[0] + min(inf, m[1] + m[2]);
  39. 	auto it = enemies.end();
  40. 	--it;
  41. 	if(*it >= all) {
  42. 		puts("-1");
  43. 		return 0;
  44. 	}
  45. 	int ans = 0;
  46. 	greedy(m[1] + m[2], 0, ans);
  47. 	greedy(m[0] + m[2], m[0], ans);
  48. 	greedy(max(m[0]+m[1], m[2]), m[1], ans);
  49. 	int one = 0, two = 0;
  50. 	for(int x : enemies) {
  51. 		if(x < m[0] + m[1]) ++one;
  52. 		if(x < m[2]) ++two;
  53. 	}
  54. 	int best = inf;
  55. 	for(int rep = 0; rep < n + 5; ++rep) {
  56. 		if(max(one, two) == (int) enemies.size()) {
  57. 			if(2 * min(one, two) >= (int) enemies.size()) best = min(best, rep + ((int) enemies.size() + 1) / 2);
  58. 			else best = min(best, rep + (int) enemies.size() - min(one, two));
  59. 		}
  60. 		for(int i = 0; i < 3; ++i) {
  61. 			auto it = enemies.lower_bound(m[i]);
  62. 			if(it != enemies.begin()) {
  63. 				--it;
  64. 				if(*it < m[0] + m[1]) --one;
  65. 				if(*it < m[2]) --two;
  66. 				enemies.erase(it);
  67. 			}
  68. 		}
  69. 	}
  70. 	printf("%d\n", ans + best);
  71. 	return 0;
  72. }
  73.  
Time limit exceeded #stdin #stdout 5s 133696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R3Oy3F
Musketeers
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!