Submission #857319

#	Time	Username	Problem	Language	Result	Execution time	Memory
857319		StefanSebez	Self Study (JOI22_ho_t2)	C++14	100 / 100	591 ms	11112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const ull inf=1e18;
int main()
{
    ll n,m;cin>>n>>m;
    ll a[n+1],b[n+1],M=0;
    for(int i=1;i<=n;i++){cin>>a[i];}
    for(int i=1;i<=n;i++){cin>>b[i];}
    ll l=1,r=inf,mid=l+(r-l)/2,res=0;
    while(l<=r)
	{
		//printf("%lld %lld %lld: ",l,mid,r);
		ull sum=0;
		for(ll i=1;i<=n;i++)
		{
			ll x,z,k=inf;
			if(a[i]<=b[i])
			{
				x=0;
				z=(mid+b[i]-1)/b[i];
				k=max(x,z);
			}
			else
			{
				x=mid/a[i];
				if(x>m) x=m;
				z=(mid-x*(a[i]-b[i])+b[i]-1)/b[i];
				k=min(k,max(x,z));
				x++;
				if(x>m) x=m;
				z=(mid-x*(a[i]-b[i])+b[i]-1)/b[i];
				k=min(k,max(x,z));
				//cout<<" {"<<x<<","<<z<<"} ";
			}
			sum+=k;
			ll k1=inf;
			for(ll j=0;j<=m;j++)
			{
				ll z=ceil((double)(mid-j*(a[i]-b[i]))/b[i]);
				k1=min(k1,max(j,z));
			}
			/*int x=0;
			if(a[i]>b[i])x=min(mid/(a[i]-b[i]),m);
			sum+=ceil((mid-x*(a[i]-b[i]))/b[i]);*/
			//cout<<"|"<<k<<" "<<k1<<"| ";
		}
		//cout<<endl;
		if(sum<=n*m)
		{
			res=mid;
			l=mid+1;
		}
		else r=mid-1;
		mid=l+(r-l)/2;
	}
	cout<<res<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:51:9: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
   51 |   if(sum<=n*m)
      |      ~~~^~~~~
Main.cpp:9:22: warning: unused variable 'M' [-Wunused-variable]
    9 |     ll a[n+1],b[n+1],M=0;
      |                      ^

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 9 / 9