Submission #1168795

#TimeUsernameProblemLanguageResultExecution timeMemory
1168795lufychopSelf Study (JOI22_ho_t2)C++20
0 / 100
253 ms5108 KiB
#include <bits/stdc++.h>

using namespace std;

bool cmp(const pair<long long,long long> a,const pair<long long,long long> b)
{
	if(max(a.first,a.second)==max(b.first,b.second))
	{
		return min(a.first,a.second)>min(b.first,b.second);
	}
	return max(a.first,a.second)>max(b.first,b.second);
}

int main(void)
{
	long long n,m,l,r,ans=-1,mid,mn;
	cin>>n>>m;
	vector<pair<long long,long long>> v(n);
	for(int i=0;i<n;i++)
	{
		cin>>v[i].first;
	}
	for(int i=0;i<n;i++)
	{
		cin>>v[i].second;
		v[i].first=max(v[i].first,v[i].second);
	}
	sort(v.begin(),v.end(),cmp);
//	for(int i=0;i<n;i++)
//	{
//		cout<<v[i].first<<" "<<v[i].second<<"\n";
//	}
	l=0;
	r=1e18;
	while(l<=r)
	{
		mid=l+(r-l)/2;
		mn=m*n;
		long long cntfree=0,t;
		for(int i=0;i<n;i++)
		{
			t=(mid/v[i].first)+((mid%v[i].first)!=0);
			if(t<=m)
			{
				cntfree=cntfree+m-t;
			}
			else
			{
				t=mid-v[i].first*m;
				t=(t/v[i].second)+((t%v[i].second)!=0);
				cntfree=cntfree-t;
			}
		}
		if(cntfree>=0)
		{
			ans=mid;
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	cout<<ans;
	return 0;
}
/*
3 3
19 4 5
2 6 2

19 4 5
2 6 2
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...