fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define cincout
  3. #define min(a,b) ((a) < (b) ? (a) : (b))
  4. #define max(a,b) ((a) > (b) ? (a) : (b))
  5. #define abs(x) ((x) < 0 ? -(x) : (x))
  6. using namespace std;
  7. typedef long long ll;
  8.  
  9. priority_queue <ll, vector <ll>, greater <ll> > dryer;
  10. ll tmp_ans,mid,le,ri,tmp_processed,t,l,n,m,d,wash[100005],tmp;
  11. int tcs;
  12. vector <ll> washes;
  13.  
  14. int main() {
  15. 	#ifdef cincout
  16. 		cin.sync_with_stdio(0);
  17. 		cin.tie(0);
  18. 	#endif
  19. 	cin >> t; tcs=0;
  20. 	while (t--) {
  21. 		++tcs;
  22. 		cin >> l >> n >> m >> d;
  23. 		for (int i=0;i<n;++i) cin >> wash[i];
  24. 		while (!dryer.empty()) dryer.pop();
  25. 		m=min(l,m);
  26. 		tmp_ans=3000000000000000LL;
  27. 		le=0; ri=3000000000000000LL;
  28. 		while (le<=ri) {
  29. 			mid=(le+ri)>>1;
  30. 			tmp_processed=0;
  31. 			for (int i=0;i<n;++i) tmp_processed+=mid/wash[i];
  32. 			if (tmp_processed>=l) {
  33. 				tmp_ans=min(mid,tmp_ans);
  34. 				ri=mid-1;
  35. 			} else le=mid+1;
  36. 		}
  37. 		washes.clear();
  38. 		for (int i=0;i<n;++i) {
  39. 			tmp=tmp_ans/wash[i];
  40. 			for (ll j=1;j<=tmp;++j) washes.push_back(wash[i]*j);
  41. 		}
  42. 		sort(washes.begin(),washes.end());
  43. 		for (int i=0;i<m;++i) dryer.push(0);
  44. 		for (int i=0;i<l;++i) {
  45. 			tmp=dryer.top();
  46. 			dryer.pop();
  47. 			dryer.push(max(tmp,washes[i])+d);
  48. 		}
  49. 		while (!dryer.empty()) {
  50. 			tmp=dryer.top();
  51. 			dryer.pop();
  52. 		}
  53. 		cout << "Case #" << tcs << ": " << tmp << '\n';
  54. 	}
  55. 	return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5
1 1 1 34
1200
2 3 2 10
100 10 1
3 3 3 3
1 2 3
4 2 2 7
5 8
999 1 999 6
3
stdout
copy 
Case #1: 1234
Case #2: 12
Case #3: 5
Case #4: 22
Case #5: 3003
https://ideone.com/yKWVTL
language:
C++14 (gcc 8.3)
created:
10 hours 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!