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, int 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.         sum+=((tickets[i]*programs[i])*1LL)/100LL;
  43.     }
  44.     return sum>=k;
  45. }
  46.  
  47. void solve() {
  48.     int n; cin >> n;
  49.  
  50.     vector<int> tickets(n);
  51.     for(int i=0; i<n; i++) cin >> tickets[i];
  52.     sort(all(tickets), greater<int>());
  53.  
  54.     pair<int, int> x;
  55.     int a, b; cin >> a >> b; x=make_pair(a, b);
  56.     pair<int, int> y;
  57.     int c, d; cin >> c >> d; y=make_pair(c, d);
  58.  
  59.     ll k; cin >> k;
  60.  
  61.     int left=1, right=n, ans=-1;
  62.     while(left<=right) {
  63.         int mid=(left+right)/2;
  64.  
  65.         if(test(tickets, k, mid, x, y)) {
  66.             right=mid-1;
  67.             ans=mid;
  68.         } else left=mid+1;
  69.     }
  70.  
  71.     cout << ans << endl;
  72. }
  73.  
  74. int main() {
  75. 	fast();
  76.  
  77. 	int t=1;
  78. 	cin >> t;
  79. 	while(t--)
  80.     solve();
  81.  
  82.  
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/LMO8VS
language:
C++ (gcc 8.3)
created:
6 hours 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!