Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- signed main(int argc, char const *argv[])
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t;
- cin >> t;
- while (t--)
- {
- int n, c;
- cin >> n >> c;
- int total = 0;
- vector<int> a(n);
- for (auto &elem : a)
- {
- cin >> elem;
- total += elem;
- }
- vector<int> v;
- v.push_back(0);
- for (int i = 1; i < n; i++)
- v.push_back(a[i]);
- sort(v.begin(), v.end());
- v.push_back(0);
- vector<int> pre(n + 1, 0);
- vector<int> suf(n + 1, 0);
- for (int i = 1; i <= n - 1; i++)
- {
- pre[i] += pre[i - 1] + v[i];
- }
- for (int i = n - 1; i >= 1; i--)
- {
- suf[i] += suf[i + 1] + v[i];
- }
- int sum = a[0];
- int ans = 1;
- for (int i = 0; i <= n - 1; i++)
- {
- int cost = min((sum + pre[i]) * (total - sum - pre[i]), (sum + suf[n - i]) * (total - sum - suf[n - i]));
- if (cost <= c)
- {
- ans = i + 1;
- break;
- }
- }
- cout << ans << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement