레이팅 미적용현재 소들이 이용할 수 있는 데이팅 웹사이트들(예: eHarmoony, Moosk, Plenty of Cows)이 영 신통치 않다고 느낀 농부 존은, 다양한 공통 관심사에 따라 암소와 황소를 매칭하는 고급 독점 매칭 알고리즘에 기반한 새로운 소 데이팅 사이트를 열기로 한다.
밸런타인데이 헛간 무도회의 파트너를 찾고 있는 베시는 이 사이트를 이용해 보기로 했다. 계정을 만들자, 농부 존의 알고리즘은 베시에게 \(N\)명의 가능한 매칭 상대 목록을 주었다 (\(1\leq N \leq 10^6\)). 목록을 살펴본 베시는 각 황소가 무도회 초대를 수락할 확률이 \(p_i\) (\(0
베시는 목록의 연속한 구간에 속한 모든 황소에게 초대장을 보내기로 한다. 언제나 정숙한 베시는 파트너가 정확히 한 명이기를 원한다. 베시가 적절한 구간을 선택했을 때, 정확히 하나의 초대가 수락될 확률의 최댓값을 구하는 것을 도와주자.
문제 제공: Ethan Guo
문제 제공: Ethan Guo
첫째 줄에 \(N\) (\(1 \leq N \leq 10^6\))이 주어진다. 남은 \(N\)개의 줄 각각에는 \(p_i\)에 \(10^6\)을 곱한 값이 주어지며, 이는 정수이다.
적어도 25%의 테스트 케이스에서는 추가로 \(N \leq 4000\)이 보장된다.
정확히 하나의 초대가 수락될 확률의 최댓값에 \(10^6\)을 곱한 값을 내림하여 정수로 출력한다.
cowdate.in · 출력을 쓸 파일 cowdate.out3
300000
400000
350000470000The maximal probability results from selecting the interval from the 2nd to the
3rd cow.
As a note, you should be somewhat careful with floating point precision when
solving this problem. We advise using at least "doubles" (64-bit floating-point
numbers) and not "floats" (32-bit floating point numbers).
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > February > Platinum