Codeforces Round 886 (Div. 4) 1850E - Cardboard for Pictures Solution

 

Problem Link: https://codeforces.com/problemset/problem/1850/E

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. #define int long long
5. const int mx = 2e5 + 9 ;
6. int a[mx] , n , c ;
7. bool ok (int w ){
8. int total = 0 ;
9. for( int i = 0 ; i < n ; i++){
10. int side = a[i] + 2 * w ;
11. int area = side * side ;
12. if (total + area >= c) return true ;
13. total += area ;
14. }
15. return false ;
16. }
17. int32_t main() {
18. ios_base::sync_with_stdio(0);
19. cin.tie(0);
20. int t;
21. cin >> t;
22. while (t--) {
23. cin >> n >> c ;
24. for ( int i = 0 ; i < n ; i++){
25. cin >> a[i] ;
26. }
27. int low = 1 , high = 1e9 + 9 ;
28. int ans = 0 ;
29. while(low <= high){
30. int mid = ( low + high ) / 2 ;
31. if(ok(mid)){
32. ans = mid ;
33. high = mid - 1 ;
34. }
35. else{
36. low = mid + 1 ;
37. }
38. }
39. cout << ans <<'\n' ;
40. }
41. return 0 ;
42. }