fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int int64_t
  6. const int maxn = 2e5, inf = 2e18;
  7. int a[maxn], b[maxn];
  8.  
  9. signed main()
  10. {
  11. 	ios::sync_with_stdio(0);
  12. 	cin.tie(0);
  13. 	int n, k;
  14. 	cin >> n >> k;
  15. 	for(int i = 0; i < n; i++)
  16. 		cin >> a[i];
  17. 	for(int i = 0; i < n; i++)
  18. 		cin >> b[i], a[i] *= b[i];
  19. 	int l = 0, r = 1 + *max_element(a, a + n);
  20. 	while(r - l > 1)
  21. 	{
  22. 		int m = (l + r) / 2;
  23. 		int t = 0;
  24. 		for(int i = 0; i < n; i++)
  25. 			t += max((int)0, (a[i] - m + b[i] - 1) / b[i]);
  26. 		if(t >= k)
  27. 			l = m;
  28. 		else
  29. 			r = m;
  30. 	}
  31. 	l = r;
  32. 	for(int i = 0; i < n; i++)
  33. 		k -= max((int)0, (a[i] - l + b[i] - 1) / b[i]),
  34. 		a[i] -= max((int)0, (a[i] - l + b[i] - 1) / b[i]) * b[i];
  35. 	set<pair<int, int>> que;
  36. 	for(int i = 0; i < n; i++)
  37. 		que.insert({-a[i], i});
  38. 	if(n == 1)
  39. 		a[0] -= min(a[0], b[0] * k);
  40. 	else
  41. 	while(k--)
  42. 	{
  43. 		int v = que.begin()->second;
  44. 		if(a[v] == 0)
  45. 			break;
  46. 		que.erase(que.begin());
  47. 		a[v] -= b[v];
  48. 		que.insert({-a[v], v});
  49. 	}
  50. 	for(int i = 0; i < n; i++)
  51. 		cout << a[i] / b[i] << " ";
  52.  
  53. 	return 0;
  54. }
Runtime error #stdin #stdout 0s 6580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tdG8Iv
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!