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
stdin
Standard input is empty
stdout
Standard output is empty