fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast() ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  5. #define all(x) (x).begin(),(x).end()
  6. #define yesc cout << "YES\n"
  7. #define noc cout << "NO\n"
  8. #define yesp printf("YES\n")
  9. #define nop printf("NO\n")
  10. #define PI 3.141592653589793238462643383279502884L
  11. typedef long long ll;
  12.  
  13. vector<int> makeprograms(int mid, pair<int, int> x,pair<int, int> y) {
  14.     vector<int> result;
  15.  
  16.     for(int i=1; i<=mid;i++) {
  17.         if(i%x.second==0 && i%y.second==0) {
  18.             result.push_back((x.first+y.first));
  19.         }
  20.         else if(i%x.second==0) {
  21.             result.push_back(x.first);
  22.         }
  23.         else if(i%y.second==0) {
  24.             result.push_back(y.first);
  25.         }
  26.         else {
  27.             result.push_back(0);
  28.         }
  29.     }
  30.  
  31.     sort(all(result), greater<int>());
  32.  
  33.     return result;
  34. }
  35.  
  36. bool test(vector<int>& tickets, ll k, int mid, pair<int, int> x,pair<int, int> y) {
  37.  
  38.     vector<int> programs=makeprograms(mid, x, y);
  39.  
  40.     ll sum=0;
  41.     for(int i=0; i<mid;i++) {
  42.        ll temp = 1LL*tickets[i]*programs[i];
  43.        sum += temp/100;
  44.  
  45.     }
  46.     return sum>=k;
  47. }
  48.  
  49. void solve() {
  50.     int n; cin >> n;
  51.  
  52.     vector<int> tickets(n);
  53.     for(int i=0; i<n; i++) cin >> tickets[i];
  54.     sort(all(tickets), greater<int>());
  55.  
  56.     pair<int, int> x;
  57.     int a, b; cin >> a >> b; x=make_pair(a, b);
  58.     pair<int, int> y;
  59.     int c, d; cin >> c >> d; y=make_pair(c, d);
  60.  
  61.     ll k; cin >> k;
  62.  
  63.     int left=1, right=n, ans=-1;
  64.     while(left<=right) {
  65.         int mid=(left+right)/2;
  66.  
  67.         if(test(tickets, k, mid, x, y)) {
  68.             right=mid-1;
  69.             ans=mid;
  70.         } else left=mid+1;
  71.     }
  72.  
  73.     cout << ans << endl;
  74. }
  75.  
  76. int main() {
  77. 	fast();
  78.  
  79. 	int t=1;
  80. 	cin >> t;
  81. 	while(t--)
  82.     solve();
  83.  
  84.  
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
1
3
1000000000 1000000000 1000000000
50 1
50 1
3000000000
stdout
copy 
3
https://ideone.com/S7XBBy
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!