Submission #869570

#	Time	Username	Problem	Language	Result	Execution time	Memory
869570		Hakiers	Self Study (JOI22_ho_t2)	C++17	100 / 100	154 ms	11348 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 3e5 + 7;
pair<ll, ll> courses[MAXN];
ll n, m;

bool check(ll mid){
	ll tickets = n*m;
	
	for(int i = 1; i <= n; i++){
		ld tmp = mid;
		tickets -= min(m, (ll)ceil(tmp/courses[i].first));
		tmp -= min(m, (ll)ceil(tmp/courses[i].first)) * courses[i].first;

		if(tmp > 0)
			tickets -= (ll)ceil(tmp/courses[i].second);
		
		if(tickets < 0) return false;
	}
	
	return true;
}

ll BS(){

	ll l = 1, r = (m * 1e9), mid;
	
	while(l < r){
		mid = (l+r)/2;
		if(check(mid)) l = mid + 1;
		else r = mid;
	}
	
	if(!check(l)) l--;
	return l;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> courses[i].first;
	for(int i = 1; i <= n; i++){
		cin >> courses[i].second;
		courses[i].first = max(courses[i].first, courses[i].second);
	}
	
	cout << BS() << "\n";

}

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