제출 #1199967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199967		Boomyday	Seesaw (JOI22_seesaw)	C++20	67 / 100	2095 ms	6540 KiB

seesaw

//
// Created by adavy on 5/11/2025.
//


#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using db = long double;
int N; vector<db> nums, numprefs;
const db EPS = 1e-9;

db incl_sum(int l, int r){
    if (l > r) return 0;
    return numprefs[r+1] - numprefs[l];
}


bool is_good(db len){
    for(int l=0;l<N;++l) for(int r=l; r <= N;++r){
        int num_terms = r-l;
        db sm = incl_sum(0, N-1) - incl_sum(0, l-1) - incl_sum(r, N-1);
        db lb = sm/(num_terms);
        db rb = lb + len;
        db cursum = incl_sum(0, N-1);
        db start = incl_sum(0, N-1)/N;
        db curterms = N;
        if(!(lb <= start && start <= rb)){
            continue;
        }
        int lptr = 0, rptr = N-1;
        while(lptr < rptr){
            db lsum = cursum - incl_sum(lptr, lptr);
            db rsum = cursum - incl_sum(rptr, rptr);
            if (lb <= lsum/(curterms-1) && lsum/(curterms-1) <= rb){
                lptr++;
                curterms--;
                cursum -= incl_sum(lptr-1, lptr-1);
            } else if (lb <= rsum/(curterms-1) && rsum/(curterms-1) <= rb){
                rptr--;
                curterms--;
                cursum -= incl_sum(rptr+1, rptr+1);
            } else {
                break;
            }
        }
        if (lptr >= rptr){
            return true;
        }
    }
    return false;
}
int main(){
    cin >> N;
    nums.resize(N);
    numprefs.resize(N+1, 0);
    for(int i=0;i<N;++i){
        cin >> nums[i];
        numprefs[i+1] = numprefs[i] + nums[i];
    }
    db lo = 0, hi = 2e9;
    while ((hi-lo) >= EPS){
        if (is_good((hi+lo)/2)){
            hi  = (hi+lo)/2;
        } else {
            lo = (hi+lo)/2;
        }
    }
    cout << fixed << setprecision(10) << hi << endl;
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 0 / 33