fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main() {
  4. int test;
  5. cin>>test;
  6. while(test--)
  7. {
  8. int x,y,z,k,i;
  9. cin>>x>>y>>z>>k;
  10. vector<int>vec(y);
  11. vector<int>printed;
  12. for(int i=0;i<y;++i)
  13. cin>>vec[i];
  14. sort(vec.begin(),vec.end());
  15. priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
  16. int currtime = 0;
  17. i=0;
  18. int j=0;
  19. while(i<x)
  20. {
  21. if(pq.empty())
  22. {
  23. pq.push(make_pair(vec[j],j));
  24. ++j;
  25. ++i;
  26. }
  27. else
  28. {
  29. if(j<y && pq.top().first>vec[j])
  30. {
  31. pq.push(make_pair(vec[j],j));
  32. ++j;
  33. ++i;
  34. }
  35. else
  36. {
  37. int currtime=pq.top().first;
  38. int currmachine=pq.top().second;
  39. printed.push_back(currtime);
  40. pq.pop();
  41. pq.push(make_pair(currtime+vec[currmachine],currmachine));
  42. ++i;
  43. }
  44. }
  45. }
  46. while(!pq.empty())
  47. {
  48. printed.push_back(pq.top().first);
  49. pq.pop();
  50. }
  51. i=0;
  52. vector<int>finalvec;
  53. for(i=0;i<min((int)printed.size(),z);++i)
  54. pq.push(make_pair(printed[i]+k,1));
  55. while(i<printed.size())
  56. {
  57. finalvec.push_back(pq.top().first);
  58. currtime = max(pq.top().first,printed[i]);
  59. pq.pop();
  60. pq.push(make_pair(currtime+k,1));
  61. ++i;
  62. }
  63. while(!pq.empty())
  64. {
  65. finalvec.push_back(pq.top().first);
  66. pq.pop();
  67. }
  68. cout<<"answer is "<<finalvec[finalvec.size()-1]<<endl;
  69. }
  70. return 0;
  71. }
Success #stdin #stdout 0s 4508KB
stdin
3

2 1 1 34

1100

2 3 2 10

10 16 1

3 2 2 5

5 7
stdout
answer is 2234
answer is 12
answer is 15