fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using namespace chrono;
  4. using ll = long long;
  5. const bool generate_test = false;
  6. const bool validate_test = true;
  7. #define lcm(x,y) (x/__gcd(x,y)*y)
  8.  
  9. ll n, x, a, y, b, k; vector<ll> price;
  10.  
  11. // Acceped solution written by: ek3ru8m4@codeforces.com
  12.  
  13. ll ek3ru8m4_solution() {
  14.  
  15. 	ll a1, x1, b1, y1, j = 1, c1 = 0, c2 = 0, c3 = 0, l = 0;
  16.  
  17.     if (x < y) 
  18.     	a1 = b, x1 = y, b1 = a, y1 = x;
  19.     else
  20.     	a1 = a, x1 = x, b1 = b, y1 = y;
  21.  
  22.     for (x1 -= y1; l < k and j <= n; ++j) {
  23.     	if (j%a1 == 0 or j%b1 == 0)
  24. 			l += price[c3++] * y1;
  25. 		if (j%a1 == 0)
  26. 			l += price[c2++] * x1;
  27. 		if (j%a1 == 0 && j%b1 == 0)
  28. 			l += price[c1++] * y1; }
  29.  
  30.    return l < k? -1: (j-1); }
  31.  
  32. // Random Test-Case Generator
  33.  
  34. template<typename Int>
  35. struct random_variable: mt19937_64 {
  36. 	random_variable() : mt19937_64(steady_clock::now().time_since_epoch().count()) {}
  37. 	Int value(Int u, Int v) { return uniform_int_distribution<Int>(u,v)(*this); } }; 
  38.  
  39. random_variable<ll> Random; 
  40.  
  41. void generate_test_case(ll N, ll P, ll Q) {
  42.  
  43. 	price.resize(n = N); 
  44.  
  45. 	for (auto &q: price)
  46. 		q = Random.value(1,P);
  47.  
  48. 	sort(price.rbegin(),price.rend());
  49.  
  50. 	const ll sum = Random.value(2,100);
  51.  
  52. 	x = Random.value(1,sum-1), y = sum-x, 
  53. 	a = Random.value(1,n), 
  54. 	b = Random.value(1,n),
  55. 	k = Random.value(1,Q); }
  56.  
  57. void write_test_case() {
  58.  
  59. 	cout << 1 << endl << n << endl;
  60.  
  61.  	for (ll i = 0; i < n; ++i)
  62.  		cout << 100*price[i] << ' ';
  63.  
  64. 	cout << endl << x << ' ' << a << endl << y << ' ' << b << endl << k;  }
  65.  
  66. // Solution written by rpkv@codeforces.com
  67.  
  68. typedef     long double      ld;
  69. typedef     pair<ll,ll>      pll;
  70. #define     FOR(i,a,b)       for(ll i=a;i<b;i++)
  71. #define     FORE(i,a,b)      for(int i=a;i<=b;i++)
  72. #define     FORD(i,b,a)      for(int i=b;i>a;i--)
  73. #define     FORDE(i,b,a)     for(ll i=b;i>=a;i--)
  74. #define     debug(x)         cout<< '>'<<#x<<" : "<<x<<"\n";
  75. #define     debug2(x,y)      cout<< '>'<<#x<<" : "<<x<<"\n"; cout<< '>'<<#y<<" : "<<y<<"\n";
  76. #define     debug3(x,y,z)    cout<< '>'<<#x<<" : "<<x<<"\n"; cout<< '>'<<#y<<" : "<<y<<"\n";cout<< '>'<<#z<<" : "<<z<<"\n";
  77. #define     umap             unordered_map
  78. #define     uset             unordered_set
  79. #define     lb               lower_bound
  80. #define     ub               upper_bound
  81. #define     mp               make_pair
  82. #define     in               insert
  83. #define     s                second
  84. #define     f                first
  85. #define     nn               cout<<"\n"
  86. #define     pb               push_back
  87. #define     testcase         int t;cin>>t;while(t--)
  88. #define     gcd(a,b)         __gcd(a,b)
  89. #define     maxv             INT_MAX
  90. #define     minv             INT_MIN
  91. #define     MOD              1000000007
  92. #define     FastIO           ios_base::sync_with_stdio(false);cin.tie(NULL)
  93. #define     here             cout<<"I'm here\n";
  94. #define     flush            fflush(stdout);
  95.  
  96. struct custom_hash {
  97.     static uint64_t splitmix64(uint64_t x) {
  98.         x += 0x9e3779b97f4a7c15;
  99.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  100.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  101.         return x ^ (x >> 31);
  102.     }
  103.     size_t operator()(uint64_t x) const {
  104.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  105.         return splitmix64(x + FIXED_RANDOM);
  106.     }
  107. };
  108.  
  109. template<class T> void dispvector(vector<T> v){for(int i=0;i<v.size();i++) cout<<v[i]<<" "; nn;}
  110. template<class T> void disparray(T *v, int n){for(int i=0;i<n;i++) cout<<v[i]<<" "; nn;}
  111. template<class T> int sizeofarr(T *v){return sizeof(v)/sizeof(T);}
  112.  
  113. void read_test_case() {
  114.  
  115. 	cin >> n, price.resize(n); 
  116.  
  117. 	for (auto &q: price) 
  118. 		cin >> q, q /= 100;
  119.  
  120. 	sort(price.rbegin(),price.rend());
  121.  
  122. 	cin >> x >> a >> y >> b >> k; }
  123.  
  124. ll rpkv_solution() {
  125.  
  126.     	queue<ll> price1q;
  127.         queue<ll> price2q;
  128.         queue<ll> price3q;
  129.         ll cost = 0;
  130.         ll p1 = x+y;
  131.         ll p2,p3;
  132.         ll mlcm = lcm(a,b);
  133.         ll ans = -1;
  134.         if(x > y){
  135.             p2 = x;
  136.             p3 = y;
  137.             ll idx = 0;
  138.             FOR(i,0,n) {
  139.                 if((i+1)%mlcm == 0){
  140.                     if(price2q.size() == 0 && price3q.size() == 0){
  141.                         cost += 1ll * price[idx] * p1;
  142.                         idx++;
  143.                     }
  144.                     else if(price2q.size()== 0){
  145.                         cost += 1ll * price3q.front() * (p1-p3);
  146.                         price3q.pop();
  147.                         price3q.push(price[idx]);
  148.                         idx++;
  149.                     }
  150.                     else{
  151.                         cost += 1ll * price2q.front() * (p1-p2);
  152.                         price2q.pop();
  153.                         if(price3q.size() == 0){
  154.                             price2q.push(price[idx]);
  155.                             cost += 1ll * price[idx]*p2;
  156.                             idx++;
  157.                         }else{
  158.                             price2q.push(price3q.front());
  159.                             cost += 1ll * price3q.front() * (p2-p3);
  160.                             price3q.pop();
  161.                             price3q.push(price[idx]);
  162.                             cost += 1ll * price[idx]*p3;
  163.                             idx++;
  164.                         }
  165.                     }
  166.                     if(cost >= k){
  167.                         ans = i+1;
  168.                         break;
  169.                     }
  170.                 }else if((i+1)%a == 0){
  171.                     if(price3q.size() == 0){
  172.                         price2q.push(price[idx]);
  173.                         cost += 1ll * price[idx]*p2;
  174.                         idx++;
  175.                     }else{
  176.                         price2q.push(price3q.front());
  177.                         cost += 1ll * price3q.front() * (p2-p3);
  178.                         price3q.pop();
  179.                         price3q.push(price[idx]);
  180.                         cost += 1ll * price[idx]*p3;
  181.                         idx++;
  182.                     }
  183.                     if(cost >= k){
  184.                         ans = i+1;
  185.                         break;
  186.                     }
  187.                 }else if((i+1)%b == 0){
  188.                     price3q.push(price[idx]);
  189.                     cost += 1ll * price[idx]*p3;
  190.                     idx++;
  191.                     if(cost >= k){
  192.                         ans = i+1;
  193.                         break;
  194.                     }
  195.                 }
  196.             }
  197.         }
  198.         else{
  199.             p2 = y;
  200.             p3 = x;
  201.             ll idx = 0;
  202.             FOR(i,0,n) {
  203.                 if((i+1)%mlcm == 0){
  204.                     if(price2q.size() == 0 && price3q.size() == 0){
  205.                         cost += 1ll * price[idx] * p1;
  206.                         idx++;
  207.                     }
  208.                     else if(price2q.size()== 0){
  209.                         cost += 1ll * price3q.front() * (p1-p3);
  210.                         price3q.pop();
  211.                         price3q.push(price[idx]);
  212.                         idx++;
  213.                     }
  214.                     else{
  215.                         cost += 1ll * price2q.front() * (p1-p2);
  216.                         price2q.pop();
  217.                         if(price3q.size() == 0){
  218.                             price2q.push(price[idx]);
  219.                             cost += 1ll * price[idx]*p2;
  220.                             idx++;
  221.                         }else{
  222.                             price2q.push(price3q.front());
  223.                             cost += 1ll * price3q.front() * (p2-p3);
  224.                             price3q.pop();
  225.                             price3q.push(price[idx]);
  226.                             cost += 1ll * price[idx]*p3;
  227.                             idx++;
  228.                         }
  229.                     }
  230.                     if(cost >= k){
  231.                         ans = i+1;
  232.                         break;
  233.                     }
  234.                 }else if((i+1)%b == 0){
  235.                     if(price3q.size() == 0){
  236.                         price2q.push(price[idx]);
  237.                         cost += 1ll * price[idx]*p2;
  238.                         idx++;
  239.                     }else{
  240.                         price2q.push(price3q.front());
  241.                         cost += 1ll * price3q.front() * (p2-p3);
  242.                         price3q.pop();
  243.                         price3q.push(price[idx]);
  244.                         cost += 1ll * price[idx]*p3;
  245.                         idx++;
  246.                     }
  247.                     if(cost >= k){
  248.                         ans = i+1;
  249.                         break;
  250.                     }
  251.                 }else if((i+1)%a == 0){
  252.                     price3q.push(price[idx]);
  253.                     cost += 1ll * price[idx]*p3;
  254.                     idx++;
  255.                     if(cost >= k){
  256.                         ans = i+1;
  257.                         break;
  258.                     }
  259.                 }
  260.             }
  261.         }
  262.  
  263.     return ans;
  264. }
  265.  
  266. int main() {
  267.  
  268.  
  269. 	if (generate_test) {
  270. 		do 
  271. 			generate_test_case(10,100,1000); 
  272. 		while (ek3ru8m4_solution() == rpkv_solution());
  273.  
  274. 		write_test_case(); }
  275. 	else if (validate_test) {
  276. 		testcase {
  277. 			read_test_case(),
  278. 			write_test_case(),
  279. 			cout << endl << "ek3ru8m4's solution = " << ek3ru8m4_solution(),
  280. 			cout << endl << "rpkv's solution = " << rpkv_solution(); } }
  281. 	else {
  282. #ifndef ONLINE_JUDGE
  283.     	freopen("input.txt", "r", stdin);
  284.     	freopen("output.txt", "w", stdout);
  285. #endif
  286.     	FastIO;
  287.     	testcase{ read_test_case(), cout << rpkv_solution() <<"\n"; } } }
  288.  
  289.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
1
10
9600 9400 9300 9000 8400 6400 5500 4400 3100 2400 
1 1
1 5
536
stdout
copy 
1
10
9600 9400 9300 9000 8400 6400 5500 4400 3100 2400 
1 1
1 5
536
ek3ru8m4's solution = 5
rpkv's solution = 7
https://ideone.com/s4H6a7
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!