fork download 
  1.  
  2. #include<bits/stdc++.h>
  3. #define all(x) x.begin(), x.end()
  4. #define pb(x) push_back(x)
  5. #define cout2(x, y) cout << x << " " << y << endl
  6. #define N 200005
  7.  
  8. using namespace std;
  9.  
  10. int t[N];
  11. int n, m;
  12.  
  13. vector<int> type_machine[1005];
  14. vector<pair<int, long long> > sum[1001][1001];
  15.  
  16. long long limit = 1000000000LL;
  17.  
  18. bool can(long long temp, int need){
  19.  
  20. 	vector<pair<int, long long> >::iterator it;
  21.  
  22. 	long long total = 0, lenMachine;
  23. 	int l = int(min(limit, temp));
  24.  
  25. 	for(int i = 1; i <= 1000; i++){
  26.  
  27. 		if(type_machine[i].size() == 0)continue;
  28.  
  29. 		// we use upper bound to chose the correct sum range given some time "temp"
  30. 		it = upper_bound(all(sum[i][temp%i]), make_pair(l, limit)); 
  31. 		if(it == sum[i][temp%i].begin())continue;
  32.  
  33. 		it--;
  34. 		lenMachine = it - sum[i][temp%i].begin() + 1;
  35.  
  36. 		total += (temp/i) * lenMachine + (it->second);
  37. 	}
  38. 	return total >= need;
  39. }
  40.  
  41.  
  42.  
  43. int main(){
  44.  
  45.  
  46. 	cin >> n >> m;
  47.  
  48. 	for(int i = 0; i < n; i++)	
  49. 		scanf("%d", &t[i]);
  50.  
  51.  
  52. 	sort(t, t + n);
  53. 	//after the greedy step of sorting to get as many working machines as we can
  54. 	//we need to evaluate for certain x copies: 
  55. 	// x/t[0] + (x - t[0])/t[1] + (x - 2*t[0])/t[2] + .....
  56.  
  57.  
  58. 	for(long long i = 0; i < n; i++)
  59. 		type_machine[t[i]].pb(i * t[0]);
  60.  
  61. 	long long aux, add, cur;
  62.  
  63. 	for(int i = 1; i <= 1000; i++){
  64.  
  65. 		if(type_machine[i].size() == 0)continue;
  66. 		for(int j = 0; j < i; j++){ //possible reminder for some number of copies when you are using machine i
  67.  
  68. 			cur = 0;
  69. 			for(int k = 0; k < type_machine[i].size(); k++){
  70.  
  71. 				aux = j - type_machine[i][k];
  72.  
  73. 				if(aux >= 0)add = aux/i;
  74. 				else{
  75.  
  76. 					if(aux%i == 0)add = aux/i;
  77. 					else add = aux/i - 1;
  78. 				}
  79.  
  80. 				cur += add;
  81. 				sum[i][j].pb(make_pair(type_machine[i][k], cur));
  82. 			}
  83. 		}
  84. 	}
  85.  
  86. 	int need;
  87. 	for(int i = 0; i < m; i++){
  88.  
  89. 		scanf("%d", &need);
  90. 		long long lo = 0, hi = 1000000000000LL, me;
  91.  
  92. 		while(lo < hi){
  93.  
  94. 			me = lo + (hi - lo)/2;
  95. 			if(can(me, need))hi = me;
  96. 			else lo = me + 1;
  97. 		}
  98.  
  99.  
  100. 		printf("%I64d\n", lo);
  101. 	}
  102.  
  103. }
  104.  
Success #stdin #stdout 0s 16008KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/dSHk6e
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!