파일 업로드

데이팅 사이트

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

현재 서비스 중인 데이팅 웹사이트들에 만족하지 못한 한 개발자는 다양한 공통의 관심사에 따라 짝짓는 매칭 알고리즘을 기반으로 한 새로운 데이팅 사이트를 출시하기로 결정하였습니다.

발렌타인 데이에 데이트할 파트너를 찾고 있는 화영은 이 사이트를 이용해보기로 했습니다. 그녀가 계정을 만든 후, 데이팅 사이트의 알고리즘은 그녀에게 NN 개의 가능한 매칭 (1N1061 \leq N \leq 10^6) 리스트를 제공했습니다. 목록을 훑어 보면서 화영은 리스트의 사람들이 그녀의 데이트 초대를 수락할 확률이 pip_i (0\ltpi<10\ltp_i\lt1)라는 사실을 알았습니다.

화영은 목록의 연속적인 구간에 있는 각 사람에게 초대장을 보내기로 결정합니다. 그녀는 정확히 한 명의 파트너를 원합니다. 그녀가 올바른 구간을 선택한다면, 정확히 한 명의 초대장을 수락받을 최대 확률을 찾아 화영을 도와주세요.

💻 입력

입력의 첫 번째 줄에는 NN (1N1061 \leq N \leq 10^6)이 포함되어 있습니다. 

나머지 NN 줄 각각에는 10610^6pip_i가 포함되어 있으며, 이는 정수입니다.

테스트 케이스의 적어도 25%에서는 N4000N \leq 4000이 보장됩니다.

🖨️ 출력

받아들여진 정확히 하나의 초대를 받는 최대 확률을 10610^6번 곱하여, 가장 가까운 정수로 반올림하여 출력합니다.


💻 예제 입력 1
3
300000
400000
350000
🖨️ 예제 출력 1
470000

💡 힌트

최대 확률은 2번째에서 3번째 사람의 구간을 선택함으로써 얻어집니다.

참고로 이 문제를 푸는 데에는 부동소수점 정밀도에 약간 신경을 써야 합니다. 

우리는 적어도 '더블' (64비트 부동소수점 숫자)을 사용하고 '플로트' (32비트 부동소수점 숫자)는 사용하지 않는 것을 권장합니다.


출처: USACO 2019 February Contest, Platinum Problem 1. Cow Dating