fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int	long long
  4. #define fastIO	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  5. #define fileIO	freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  6.  
  7.  
  8. struct asst
  9. {
  10. 	int t, z, y;
  11. };
  12.  
  13. int countMaxBalloons(int t, int z, int y, int Time)
  14. {
  15. 	int batchTime = (z * t) + y;
  16. 	int batchCount = (Time / batchTime);
  17. 	int remTime = Time % batchTime;
  18. 	int totalBalloons = 0;
  19. 	totalBalloons += (batchCount * z);
  20. 	if (remTime != 0) {
  21. 		if (remTime / t >= z) {
  22. 			totalBalloons += z;
  23. 		}
  24. 		else {
  25. 			totalBalloons += (remTime / t);
  26. 		}
  27. 	}
  28. 	return totalBalloons;
  29. }
  30.  
  31. bool isBalloonPossible(int t, int z, int y, int balloons, int Time)
  32. {
  33. 	int batchTime = (z * t) + y;
  34. 	int batches = balloons / z;
  35. 	bool ok = (balloons % z == 0) ? 1 : 0;
  36. 	int currTime = 0;
  37. 	if (ok) {
  38. 		batches -= 1;
  39. 		currTime = (batchTime * batches) + (z * t);
  40. 	}
  41. 	else {
  42. 		currTime = (batchTime * (batches)) + ((balloons % z) * t);
  43. 	}
  44. 	return (currTime <= Time);
  45. }
  46.  
  47.  
  48. bool isPossible(asst *assistant, int n, int m, int Time)
  49. {
  50. 	int totalBalloons = 0;
  51. 	for (int i = 0; i < n; i++) {
  52. 		int t = assistant[i].t;
  53. 		int z = assistant[i].z;
  54. 		int y = assistant[i].y;
  55. 		int lo = 0, hi = (int) 1e9;
  56. 		while (hi > lo + 1) {
  57. 			int balloons = (lo + hi) >> 1;
  58. 			if (isBalloonPossible(t, z, y, balloons, Time)) {
  59. 				lo = balloons;
  60. 			}
  61. 			else {
  62. 				hi = balloons;
  63. 			}
  64. 		}
  65. 		totalBalloons += lo;
  66. 	}
  67. 	return (totalBalloons >= m);
  68. }
  69.  
  70.  
  71. int32_t main()
  72. {
  73. 	fastIO
  74. 	// fileIO
  75.  
  76. 	int m, n;
  77. 	cin >> m >> n;
  78. 	asst assistant[n];
  79. 	for (int i = 0; i < n; i++) {
  80. 		cin >> assistant[i].t >> assistant[i].z >> assistant[i].y;
  81. 	}
  82. 	int minTime = -1, maxTime = (int) 1e9;
  83. 	while (maxTime > minTime + 1) {
  84. 		int Time = (minTime + maxTime) >> 1;
  85. 		if (isPossible(assistant, n, m, Time)) {
  86. 			maxTime = Time;
  87. 		}
  88. 		else {
  89. 			minTime = Time;
  90. 		}
  91. 	}
  92. 	cout << maxTime << endl;
  93. 	int count[n];
  94. 	memset(count, 0, sizeof count);
  95. 	for (int i = 0; i < n; i++) {
  96. 		int t = assistant[i].t;
  97. 		int z = assistant[i].z;
  98. 		int y = assistant[i].y;
  99. 		count[i] = countMaxBalloons(t, z, y, maxTime);
  100. 	}
  101. 	int totalBalloons = 0;
  102. 	for (int i = 0; i < n; i++) {
  103. 		if (totalBalloons + count[i] <= m) {
  104. 			cout << count[i] << " ";
  105. 			totalBalloons += count[i];
  106. 		}
  107. 		else {
  108. 			if (totalBalloons == m) {
  109. 				cout << 0 << " ";
  110. 			}
  111. 			else {
  112. 				cout << (m - totalBalloons) << " ";
  113. 				totalBalloons = m;
  114. 			}
  115. 		}
  116. 	}
  117. 	cout << endl;
  118.  
  119. 	return 0;
  120. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
1 2
2 1 1
1 1 2
stdout 
1
0 1
https://ideone.com/m9VWJq
language:
C++14 (gcc 8.3)
created:
19 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!