백준 3079 임국심사

https://www.acmicpc.net/problem/3079

이 정도 시간이면 충분하니? 물어보고 충분하면 시간을 줄이고 충분하지 않으면 시간을 늘려주는 대표적인 이분탐색 문제입니다.

nlog(m) 코드인데 시간초과가 나기에 무슨일인가 싶었는데 함정이 있더군요. 심사대의 개수와 걸리는 시간이 $10^9$ 이라 최대 시간은 long long 범위입니다. (int 형으로 코드를 짜면 r을 늘리다가 오버플로우로 인한 무한루프에 빠지게 됩니다.)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int SZ=100005;
ll arr[SZ];
int n; ll m;
bool myf(ll t){
	ll x=0;
	for(int i=1;i<=n;i++) x+=(t/arr[i]);
	return m<=x;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	ll l=1, r=1LL<<60;
	ll ans=r;
	while(l<=r){
		ll mm=(l+r)/2;
		if(myf(mm)){
			r=mm-1;
			ans=min(ans,mm);
		}
		else l=mm+1;
	}
	cout<<ans;
	return 0;
}