실행 시간 제한 | 메모리 제한 |
---|---|
2 초 | 512 MB |
현재 서비스 중인 데이팅 웹사이트들에 만족하지 못한 한 개발자는 다양한 공통의 관심사에 따라 짝짓는 매칭 알고리즘을 기반으로 한 새로운 데이팅 사이트를 출시하기로 결정하였습니다.
발렌타인 데이에 데이트할 파트너를 찾고 있는 화영은 이 사이트를 이용해보기로 했습니다. 그녀가 계정을 만든 후, 데이팅 사이트의 알고리즘은 그녀에게 개의 가능한 매칭 () 리스트를 제공했습니다. 목록을 훑어 보면서 화영은 리스트의 사람들이 그녀의 데이트 초대를 수락할 확률이 ()라는 사실을 알았습니다.
화영은 목록의 연속적인 구간에 있는 각 사람에게 초대장을 보내기로 결정합니다. 그녀는 정확히 한 명의 파트너를 원합니다. 그녀가 올바른 구간을 선택한다면, 정확히 한 명의 초대장을 수락받을 최대 확률을 찾아 화영을 도와주세요.
입력의 첫 번째 줄에는 ()이 포함되어 있습니다.
나머지 줄 각각에는 번 가 포함되어 있으며, 이는 정수입니다.
테스트 케이스의 적어도 25%에서는 이 보장됩니다.
받아들여진 정확히 하나의 초대를 받는 최대 확률을 번 곱하여, 가장 가까운 정수로 반올림하여 출력합니다.
3 300000 400000 350000
470000
최대 확률은 2번째에서 3번째 사람의 구간을 선택함으로써 얻어집니다.
참고로 이 문제를 푸는 데에는 부동소수점 정밀도에 약간 신경을 써야 합니다.
우리는 적어도 '더블' (64비트 부동소수점 숫자)을 사용하고 '플로트' (32비트 부동소수점 숫자)는 사용하지 않는 것을 권장합니다.
출처: USACO 2019 February Contest, Platinum Problem 1. Cow Dating