fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file