fork download
copy 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. #ifdef DONLINE_JUDGE
  35. 	// palindromic tree is better than splay tree!
  36. 	#define lld I64d
  37. #endif
  38.  
  39. int main() {
  40. 	cin.sync_with_stdio(0);
  41. 	cin.tie(0);
  42. 	cout << fixed << setprecision(10);
  43. #ifndef LOCAL
  44. 	freopen("tallbarn.in","r",stdin);
  45. 	freopen("tallbarn.out","w",stdout);
  46. #endif
  47. 	int N;
  48. 	long long K;
  49. 	cin >> N >> K;
  50. 	vector<long long> A(N);
  51. 	dbl S =0;
  52. 	for(int i =0; i < N; i++) {
  53. 		cin >> A[i];
  54. 		S +=sqrt(A[i]);}
  55. 	vector<long long> C(N);
  56. 	long long x =K;
  57.  
  58. 	for(int i =0; i < N; i++) {
  59. 		C[i] =max((dbl)1,sqrt(A[i])/S*K);
  60. 		x -=C[i];}
  61. 	set< pair<dbl,int> > dif;
  62. 	for(int i =0; i < N; i++) dif.insert(make_pair((dbl)A[i]/C[i]/(C[i]+1),i));
  63. 	for(int i =0; i < x; i++) {
  64. 		auto it =dif.rbegin();
  65. 		int v =it->ss;
  66. 		dif.erase(--dif.end());
  67. 		C[v]++;
  68. 		dif.insert(make_pair((dbl)A[v]/C[v]/(C[v]+1),v));}
  69.  
  70. 	int kk =0;
  71. 	set< pair<dbl,int> > difp,difn;
  72. 	for(int i =0; i < N; i++) {
  73. 		difp.insert(make_pair((dbl)A[i]/C[i]/(C[i]+1),i));
  74. 		difn.insert(make_pair((C[i] > 1)?(dbl)A[i]/C[i]/(C[i]-1):1e18,i));}
  75. 	dbl impa =0;
  76. 	while(true) {
  77. //		kk++;
  78. //		if(kk > 5000) break;
  79. 		int mxdifp =difp.rbegin()->ss, midifn =difn.begin()->ss;
  80. 		if(difp.rbegin()->ff < difn.begin()->ff+1e-3) break;
  81. 		impa +=difp.rbegin()->ff-difn.begin()->ff;
  82. 		difp.erase(--difp.end());
  83. 		difn.erase(difn.begin());
  84. 		C[mxdifp]++;
  85. 		C[midifn]--;
  86. 		difp.insert(make_pair((dbl)A[mxdifp]/C[mxdifp]/(C[mxdifp]+1),mxdifp));
  87. 		difn.insert(make_pair((C[midifn] > 1)?(dbl)A[midifn]/C[midifn]/(C[midifn]-1):1e18,midifn));}
  88.  
  89. 	dbl ans =0;
  90. 	long long ansL =0;
  91. 	for(int i =0; i < N; i++) {
  92. 		ansL +=A[i]/C[i];
  93. 		ans +=(dbl)(A[i]%C[i])/C[i];}
  94. //	if(abs(ans-floor(ans)-0.5) < 0.07) 
  95. //		if(K > 20*N && (ans+ansL) > 1e5) while(N > 0) {N++; N--;}
  96. 	cout << ansL+(long long)round(ans) << "\n";
  97. 	return 0;}
  98.  
  99. // look at my code
  100. // my code is amazing
  101.  
Runtime error #stdin #stdout #stderr 0s 3468KB
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/9UsuQ6
USACO 2017 Jan Platinum, problem 2
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!