fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. ll fun2(ll x,ll a[],ll b[],ll n,ll m,ll p)
  6. {
  7.     ll count=0,r=0;
  8.     for(ll i=0;i<n;i++)
  9.     {
  10.         ll pos=a[i],val=0,c=1;
  11.         while(val<=x)
  12.         {
  13.             val+=(pos*c);
  14.             if(val>x)
  15.              break;
  16.             r=max(r,val);
  17.             count++;
  18.             c++;
  19.         }
  20.     }
  21.     return r;
  22. }
  23.  
  24. ll fun1(ll x,ll a[],ll b[],ll n,ll m,ll p)
  25. {
  26.     ll count=0,r=0;
  27.     for(ll i=0;i<n;i++)
  28.     {
  29.         ll pos=a[i],val=0,c=1;
  30.         while(val<=x)
  31.         {
  32.             val+=(pos*c);
  33.             if(val>x)
  34.              break;
  35.             r=max(r,val);
  36.             count++;
  37.             c++;
  38.         }
  39.     }
  40.     ll reqd1=count;
  41.     //return reqd1; 
  42.     ll reqd2=0;
  43.     for(ll i=0;i<m;i++)
  44.     {
  45.         ll pos=b[i],val=r,c=1;
  46.         while(val<=p)
  47.         {
  48.             val+=(pos*c);
  49.             if(val>p)
  50.              break;
  51.             reqd2++;
  52.             c++;
  53.         }
  54.     }
  55.     //return reqd2;
  56.     //cout<<reqd1<<" "<<reqd2<<" here"<<endl;
  57.     return min(reqd1,reqd2);
  58. }
  59.  
  60.  
  61. ll fun(ll x,ll a[],ll b[],ll n,ll m,ll p)
  62. {
  63.     ll count=0,r=0;
  64.     for(ll i=0;i<n;i++)
  65.     {
  66.         ll pos=a[i],val=0,c=1;
  67.         while(val<=x)
  68.         {
  69.             val+=(pos*c);
  70.             if(val>x)
  71.              break;
  72.             r=max(r,val);
  73.             count++;
  74.             c++;
  75.         }
  76.     }
  77.     ll reqd1=count;
  78.     //return reqd1; 
  79.     ll reqd2=0;
  80.     for(ll i=0;i<m;i++)
  81.     {
  82.         ll pos=b[i],val=r,c=1;
  83.         while(val<=p)
  84.         {
  85.             val+=(pos*c);
  86.             if(val>p)
  87.              break;
  88.             reqd2++;
  89.             c++;
  90.         }
  91.     }
  92.     //return reqd2;
  93.     //cout<<reqd1<<" "<<reqd2<<" here"<<endl;
  94.     return (reqd1-reqd2);
  95. }
  96.  
  97. void binarysearch(ll p,ll n,ll m,ll a[],ll b[])
  98. {
  99.     ll low=0,high=p,mid=0,maxi=0,times=0;
  100.     for(ll i=0;i<n;i++)
  101.     {
  102.         ll pos=a[i],val=0,c=1;
  103.         while(val<=p)
  104.         {
  105.             val+=(pos*c);
  106.             if(val>p)
  107.              break;
  108.             maxi++;
  109.             c++;
  110.         }
  111.     }
  112.     while(low<high)
  113.     {
  114.         mid=low+(high-low)/2;
  115.         ll value=fun(mid,a,b,n,m,p);
  116.         //cout<<low<<" "<<high<<" "<<mid<<" "<<value<<" "<<maxi<<endl;
  117.         if(value>=0)
  118.         {
  119.             if(value<=maxi)
  120.             {
  121.                 maxi=value;
  122.                 times=fun2(mid,a,b,n,m,p);
  123.                 high=mid;
  124.             }
  125.             else
  126.              low=mid;
  127.         }
  128.         else
  129.         {
  130.             if(((high-low)==1))
  131.              break;
  132.             else
  133.              low=mid;
  134.         }
  135.     }
  136.     cout<<fun1(times,a,b,n,m,p)<<endl;
  137. }
  138.  
  139. int main() 
  140. {
  141. 	int t;
  142. 	scanf("%d",&t);
  143. 	while(t--)
  144. 	{
  145. 	    ll p,n,m;
  146. 	    scanf("%lld",&p);
  147. 	    scanf("%lld %lld",&n,&m);
  148. 	    ll a[n];
  149. 	    ll b[m];
  150. 	    for(ll i=0;i<n;i++)
  151. 	     scanf("%lld",&a[i]);
  152. 	    for(ll i=0;i<m;i++)
  153. 	     scanf("%lld",&b[i]); 
  154. 	    binarysearch(p,n,m,a,b);
  155. 	}
  156. 	return 0;
  157. }
  158.  
Success #stdin #stdout 0s 4200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v2tR2P
language:
C++14 (gcc 8.3)
created:
5 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!