fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. #define double long double
  5.  
  6. using namespace std;
  7. const int MAXN = (1 << 20);
  8.  
  9. int n;
  10. int64_t k, a[MAXN];
  11.  
  12. void read()
  13. {
  14. 	cin >> n >> k;
  15. 	for(int i = 0; i < n; i++)
  16. 		cin >> a[i];
  17. }
  18.  
  19. double f(double p, double c, double a)
  20. {
  21. 	return p * c + a / p;
  22. }
  23.  
  24. double dp[MAXN];
  25. double lga[MAXN];
  26.  
  27. int64_t solve(double cost)
  28. {
  29. 	int64_t ret = 0;
  30. 	double lgc = log(1.0 / sqrt(cost));
  31. 	double lgk = log(k);
  32.  
  33. 	for(int i = 0; i < n; i++)
  34. 	{
  35. 		int64_t ck = (int64_t)(sqrt(a[i]) / sqrt(cost));
  36. 		if(lga[i] + lgc > lgk) return k + 1;
  37. 		int64_t low = (int64_t)ck;
  38. 		int64_t high = (int64_t)ck + 1;
  39.         double c_ret = (int64_t)1e17;
  40.         int64_t c_pos = 0;
  41.  
  42.         for(int64_t candidate = low; candidate <= high; candidate++)
  43. 			if(c_ret > f(candidate, cost, a[i]))
  44. 			{
  45. 				c_ret = f(candidate, cost, a[i]);
  46. 				c_pos = candidate;
  47. 			}
  48.  
  49. 		ret += c_pos;
  50. 		dp[i] = ((i) ? dp[i - 1] : 0) + (double)a[i] / (double)c_pos;
  51. 		if(ret > k) return ret;
  52. 	}
  53.  
  54. 	return ret;
  55. }
  56.  
  57. void solve()
  58. {
  59. 	for(int i = 0; i < n; i++)
  60. 		lga[i] = log(sqrt(a[i]));
  61.  
  62. 	double low = 0, high = 1e3, mid, ret;
  63. 	for(int ops = 0; ops < 69; ops++)
  64. 	{
  65.         mid = (low + high) / 2.0;
  66.         if(solve(mid) <= k) high = mid, ret = mid;
  67.         else low = mid;
  68. 	}
  69.  
  70. 	solve(ret);
  71. 	cout << (int64_t)(dp[n - 1] + 0.5) << endl;
  72. }
  73.  
  74. int main()
  75. {
  76. 	freopen("tallbarn.in", "r", stdin);
  77. 	freopen("tallbarn.out", "w", stdout);
  78.  
  79. 	ios_base::sync_with_stdio(false);
  80. 	cin.tie(NULL);
  81.  
  82. 	read();
  83. 	solve();
  84. 	return 0;
  85. }
Runtime error #stdin #stdout #stderr 0s 36240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/ojPGlI
language:
C++14 (gcc 8.3)
created:
7 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!