Submission #551450

#	Time	Username	Problem	Language	Result	Execution time	Memory
551450		luka1234	Self Study (JOI22_ho_t2)	C++14	100 / 100	550 ms	11600 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
ll n,m;
ll a[300001],b[300001];
bool check(ll f){
	ll raod=n*m;
	vector<ll> v;
	ll cnt=0;
	for(ll k=1;k<=n;k++){
		if(b[k]>=a[k]){
			cnt=f/b[k];
			if(f%b[k]!=0)
			   cnt++;
			if(cnt>raod)
			   return 0;
			raod-=cnt;
		}
		else{
			v.push_back(k);
		}
	}
	ll dar=0;
	for(ll ind:v){
		ll i=a[ind];
		ll j=b[ind];
		cnt=f/i;
		if(f%i!=0)
		   cnt++;
		if(cnt>m)
		   cnt=m;
		if(raod<cnt)
		   return 0;
		raod-=cnt;
		dar=f-cnt*i;
		if(dar<=0)
		   continue;
		cnt=dar/j;
		if(dar%j!=0)
		   cnt++;
		if(raod<cnt)
		   return 0;
		raod-=cnt;
	}
	if(raod<0)
	   return 0;
	else
	   return 1;
}
int main(){
	cin>>n>>m;
	for(ll k=1;k<=n;k++){
		cin>>a[k];
	}
	for(ll k=1;k<=n;k++){
		cin>>b[k];
	}
	ll l=0,r=2*1e18;
	ll md;
	bool bl;
	while(l<r){
		md=(l+r+1)/2;
		bl=check(md);
		if(bl==1){
			l=md;
		}
		else{
			r=md-1;
		}
	}
	cout<<l;
    return 0;
}

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