pratiyush7

Make Towers Equal

Oct 27th, 2021
612
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Pratiyush Mishra
  2.  
  3. #include <bits/stdc++.h>
  4. #define ull unsigned long long int
  5. #define ll long long int
  6. #define LL_MAX 9223372036854775807
  7. #define pb push_back
  8. #define pf push_front
  9. #define mp make_pair
  10. #define popb pop_back
  11. #define vl vector<ll>
  12. #define pl pair<ll,ll>
  13. #define bs(v, x) binary_search(v.begin(), v.end(), x)
  14. #define mem1(a) memset(a, -1, sizeof(a))
  15. #define popf pop_front
  16. #define p0(x) cout << x << " "
  17. #define p1(x) cout << x << '\n'
  18. #define p2(x, y) cout << x << " " << y << '\n'
  19. #define p3(x, y, z) cout << x << " " << y << " " << z << '\n'
  20. #define printv(v)                   \
  21.   for (ll i = 0; i < v.size(); ++i) \
  22.     cout << v[i] << " ";            \
  23.   cout << '\n'
  24. #define pr1(x) cout << fixed << setprecision(15) << x << '\n'
  25. #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>
  26. // ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
  27. // s.find_by_order(i)  itertor to ith element (0 indexed)
  28. #define mod 1000000007
  29. #define mod1 998244353
  30. #define fio                         \
  31.   ios_base::sync_with_stdio(false); \
  32.   cin.tie(NULL)
  33. #define get(n) \
  34.   ll n;        \
  35.   cin >> n
  36. #define getvec(v, n)         \
  37.   vector<ll> v(n);           \
  38.   for (ll i = 0; i < n; i++) \
  39.     cin >> v[i];
  40. #define getstr(s) \
  41.   string s;       \
  42.   cin >> s
  43. #define all(x) x.begin(), x.end()
  44. #define countBits(x) __builtin_popcount(x)
  45. using namespace std;
  46.  
  47. ll a, b, c, n;
  48. vector<ll> v;
  49.  
  50. ll solve(ll h)
  51. {
  52.     ll extra = 0;
  53.     ll ans = 0;
  54.     for (int i = n - 1; i >= 0; i--)
  55.     {
  56.         if (v[i] >= h)
  57.         {
  58.             extra += (v[i] - h);
  59.             continue;
  60.         }
  61.         ll req = h - v[i];
  62.         if (a + b <= c)
  63.         {
  64.             ll curr = (req * a) % mod;
  65.             ans = (ans + curr) % mod;
  66.             continue;
  67.         }
  68.         if (req <= extra)
  69.         {
  70.             ll curr = (c * req) % mod;
  71.             ans = (ans + curr) % mod;
  72.             extra -= req;
  73.         }
  74.         else
  75.         {
  76.             ll curr = (c * extra) % mod;
  77.             ll diff = req - extra;
  78.             curr = (curr + (diff * a) % mod) % mod;
  79.             ans = (ans + curr) % mod;
  80.             extra = 0;
  81.         }
  82.     }
  83.     ans = (ans + (extra * b) % mod) % mod;
  84.     return ans;
  85. }
  86.  
  87. void mainSolve()
  88. {
  89.     cin >> n >> a >> b >> c;
  90.     v.clear();
  91.     v.resize(n);
  92.     for (int i = 0; i < n; i++)
  93.         cin >> v[i];
  94.     sort(v.begin(), v.end());
  95.     ll l = v[0];
  96.     ll h = v[n - 1];
  97.     if (l == h)
  98.     {
  99.         p1(0);
  100.         return;
  101.     }
  102.     ll ans = INT_MAX;
  103.     while (l < h)
  104.     {
  105.         ll mid = (l + h) / 2ll;
  106.         ll l_solve = solve(mid);
  107.         ll r_solve = solve(mid + 1);
  108.         ans = min(ans, min(l_solve, r_solve));
  109.         if (l_solve  > r_solve)
  110.             l = mid + 1;
  111.         else
  112.             h = mid;
  113.     }
  114.     p1(ans);
  115. }
  116.  
  117. int main()
  118. {
  119.     fio;
  120. #ifndef ONLINE_JUDGE
  121.     freopen("input.txt", "r", stdin);
  122.     freopen("output.txt", "w", stdout);
  123. #endif
  124.     get(t);
  125.     //ll t = 1;
  126.     while (t--)
  127.     {
  128.         mainSolve();
  129.     }
  130.     return 0;
  131. }
  132.  
RAW Paste Data