Submission #1287300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287300		tunademayo	Self Study (JOI22_ho_t2)	C++20	25 / 100	241 ms	5264 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define ll long long 

const bool Multitest = 0;

const int N = 3e5 + 10;

ll a[N], b[N]; int n, m;

bool check(ll val)
{
	ll cnt = 0;
	
	for(int i = 1 ; i <= n ; i++)
	{
		if(a[i] < b[i])
		{
			if(b[i] * m < val) return 0;
			
			int l = 0, r = m, pos = -1;
			
			while(l <= r)
			{
				int mid = (l + r) >> 1;
				
				if(a[i] * mid + b[i] * (m - mid) >= val) l = mid + 1, pos = mid;
				else r = mid - 1;
			}
			
			if(pos == -1) return 0;
			
			cnt += pos;
			
//			cout << i << ' ' << pos << '\n';
		}
	}
	
	for(int i = 1 ; i <= n ; i++)
	{
		if(a[i] < b[i]) continue;
		
		if(a[i] * m >= val)
		{
			int l = 1, r = m, pos = 0;
			
			while(l <= r)
			{
				int mid = (l + r) >> 1;
				
				if(a[i] * mid >= val) r = mid - 1, pos = mid;
				else l = mid + 1;	
			}	
			
			pos = m - pos;
			
//			cout << i << ' ' << pos << '\n';
			
			cnt += pos;
		}
		else 
		{
			ll l = 0, r = n * m, pos = -1;
			
			while(l <= r)
			{
				ll mid = (l + r) >> 1;
			
				if(a[i] * m + b[i] * mid >= val) r = mid - 1, pos = mid;
				else l = mid + 1;
			}	
			
			if(pos == -1) return 0;
			
//			cout << i << ' ' << pos << ' ' << cnt << '\n';
			
			cnt -= pos;
		}	
	}
	
	return cnt >= 0;
}

void work()
{
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	for(int i = 1 ; i <= n ; i++) cin >> b[i];
	
	ll l = 1, r = 1e18, pos = -1;
//	
//	cout << check(7) << '\n';
//	
//	return;
	
	while(l <= r)
	{
		ll mid = (l + r) >> 1;
		
		if(check(mid)) l = mid + 1, pos = mid;
		else r = mid - 1;	
	}	
	
	cout << pos;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);	cout.tie(0);
	
	int q = 1;
	
	if(Multitest)	cin >> q;
	
	while(q--) work();
}

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