fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;
  4.  
  5. #define debug(x) cout << #x << " " << x << endl
  6.  
  7. typedef long double ldouble;
  8.  
  9. const int N = 1e5 + 10;
  10.  
  11. // adjustment 1
  12. struct frac1 {
  13. 	ldouble a, b;
  14. 	bool operator < (const frac1 &f) const {
  15. 		return (a/b) * (f.b + 1) < (f.a/f.b) * (b + 1);
  16. 	}
  17. };
  18.  
  19. // adjustment 2
  20. struct frac2 {
  21. 	ldouble a, b;
  22. 	bool operator < (const frac2 &f) const {
  23. 		return (a/b) * (f.b - 1) >= (f.a/f.b) * (b - 1);
  24. 	}
  25. };
  26.  
  27. int n;
  28. long long k;
  29. ldouble a[N], b1[N], b2[N], sum = 0.0;
  30. priority_queue <frac1> pq1;
  31. priority_queue <frac2> pq2;
  32.  
  33. int main (int argc, char const *argv[]) {
  34. 	freopen("tallbarn.in", "r", stdin);
  35. 	freopen("tallbarn.out", "w", stdout);
  36.  
  37.     scanf("%d %lld", &n, &k);
  38.     for (int i = 1; i <= n; ++i) {
  39.     	scanf("%Lf", a + i);
  40.     	sum += sqrt(a[i]);
  41.     }
  42.     ldouble t = sum/k, bsum;
  43.     for (int i = 1; i <= n; ++i) {
  44.     	b1[i] = b2[i] = sqrt(a[i])/t;
  45.     }
  46.     bsum = 0;
  47.     for (int i = 1; i <= n; ++i) {
  48.     	if (b1[i] < 1.0) b1[i] = 1.0;
  49.     	else b1[i] = floor(b1[i]);
  50.     	bsum += b1[i];
  51.     	frac1 frac;
  52.     	frac.a = a[i], frac.b = b1[i];
  53.     	pq1.push(frac);
  54.     }
  55.     long long down = floor(k - bsum + 0.5);
  56.     // debug(down);
  57.     while (down--) {
  58.     	frac1 frac = pq1.top();
  59.     	pq1.pop();
  60.     	frac.b += 1.0;
  61.     	pq1.push(frac);
  62.     }
  63.     bsum = 0;
  64.     for (int i = 1; i <= n; ++i) {
  65.     	if (b2[i] < 1.0) b2[i] = 1.0;
  66.     	else b2[i] = ceil(b2[i]);
  67.     	bsum += b2[i];
  68.     	frac2 frac;
  69.     	frac.a = a[i], frac.b = b2[i];
  70.     	pq2.push(frac);
  71.     }
  72.     // debug(bsum);
  73.     long long up = floor(bsum - k + 0.5);
  74.     // debug(up);
  75.     while (up--) {
  76.     	frac2 frac = pq2.top();
  77.     	pq2.pop();
  78.     	frac.b -= 1.0;
  79.     	pq2.push(frac);
  80.     }
  81.     ldouble res1 = 0.0, res2 = 0.0;
  82.     while (!pq1.empty()) {
  83.     	frac1 frac = pq1.top();
  84.     	pq1.pop();
  85.     	res1 += frac.a/frac.b;
  86.     }
  87.     while (!pq2.empty()) {
  88.     	frac2 frac = pq2.top();
  89.     	pq2.pop();
  90.     	res2 += frac.a/frac.b;
  91.     }
  92.     // debug(res1); debug(res2);
  93.     ldouble res = min(res1, res2);
  94.     long long ans = floor(res + 0.5);
  95.     printf("%lld\n", ans);
  96.     return 0;
  97. }
  98.  
  99.  
Success #stdin #stdout 0s 6984KB
comments (?)
stdin
copy 
2 5
10 
4
stdout
copy 
Standard output is empty
https://ideone.com/gItN6P
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!