fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. #define endl     "\n"
  5. #define inf 10000000000ll
  6.  
  7.  
  8. int Qtime(int *arr, int Q, int n) {
  9. 	int prata = 0;
  10. 	for (int i = 0; i < n; i++) {
  11. 		int x = 1;
  12. 		while ( (x * (x + 1)*arr[i]) / 2 <= Q )
  13. 			x++;
  14. 		x--;
  15. 		prata += x;
  16. 	}
  17. 	return prata;
  18. }
  19.  
  20. int32_t main()
  21. {	ios_base::sync_with_stdio(false);
  22. 	cin.tie(NULL);
  23.  
  24. 	int t;
  25. 	cin >> t;
  26. 	while (t--) {
  27. 		int tprata, n;
  28. 		cin >> tprata >> n;
  29. 		int *arr = new int[n];
  30. 		for (int i = 0; i < n; i++)
  31. 			cin >> arr[i];
  32. 		int ans = inf;
  33. 		int s = 0, e = inf;
  34. 		while (s <= e) {
  35. 			int mid = s + (e - s) / 2;
  36. 			int check = Qtime(arr, mid, n);
  37.  
  38. 			if (check >= tprata) { //valid, check for min time now
  39. 				ans = min(mid, ans);
  40. 				e = mid - 1;
  41. 			} else              //Invalid
  42. 				s = mid + 1;
  43. 		}
  44. 		cout << ans  << endl;
  45. 	}
  46. 	return 0;
  47. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
3
10
4 1 2 3 4
8
1 1
8
8 1 1 1 1 1 1 1 1
stdout
copy 
12
36
1
https://ideone.com/p0O56b
language:
C++ (gcc 8.3)
created:
5 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!