Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const int C = 1000000;
- const double err = 1e-12;
- void PlayGround() {
- int n;
- cin>>n;
- double p[n+1];
- for(int i=1; i<=n; ++i) {
- cin>>p[i];
- p[i] /= C;
- }
- double pre[n+1], presum[n+1];
- pre[0] = 1;
- presum[0] = 0;
- for(int i=1; i<=n; ++i) {
- pre[i] = pre[i-1] * (1-p[i]);
- presum[i] = presum[i-1] + p[i]/(1-p[i]);
- }
- double ans = 0;
- for(int i=1; i<=n; ++i) {
- int l = i+1, r = n;
- while(l<r) {
- int mid = (1+l+r)/2;
- double ans1 = (pre[mid] * (presum[mid]-presum[i-1])) / pre[i-1];
- double ans2 = (pre[mid-1] * (presum[mid-1]-presum[i-1])) / pre[i-1];
- if(ans1>ans2) {
- l = mid;
- } else {
- r = mid-1;
- }
- }
- if(l>n) --l;
- ans = max(ans, (pre[l] * (presum[l]-presum[i-1]))/pre[i-1]);
- }
- ans += err;
- cout<<(int)(ans*C)<<'\n';
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- freopen("cowdate.in", "r", stdin);
- freopen("cowdate.out", "w", stdout);
- PlayGround();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
