Submission #1176163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176163		GoBananas69	Seesaw (JOI22_seesaw)	C++20	0 / 100	0 ms	324 KiB

seesaw

#include <algorithm>
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;
typedef long long ll;

vector<double> p, pref;
double center(int l, int r) {
    return (pref[r] - pref[l]) / (r - l);
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int n;
    cin >> n;
    
    p.resize(n + 1);
    pref.resize(n + 1, 0);
    for (int i = 1; i <= n; i++){
        cin >> p[i];
        pref[i] = pref[i - 1] + p[i];
    }
    vector<vector<pair<double, double>>> dp(n + 1, vector<pair<double,double>>(n + 1, {0, 0}));
    for (int l = 0; l < n; l++){
        double c = center(l, l + 1);
        dp[l][l + 1] = {c, c};
    }
    
    for (int len = 2; len <= n; len++){
        for (int l = 0; l + len <= n; l++){
            int r = l + len;
            double c = center(l, r);
            
            auto L = dp[l + 1][r];
            pair<double, double> currL = { min(c, L.first), max(c, L.second) };
            double q1 = currL.second - currL.first;
            
            auto R = dp[l][r - 1];
            pair<double, double> currR = { min(c, R.first), max(c, R.second) };
            double q2 = currR.second - currR.first;
            
            if (q1 < q2)
                dp[l][r] = currL;
            else
                dp[l][r] = currR;
        }
    }
    
    double res = dp[0][n].second - dp[0][n].first;
    cout << fixed << setprecision(10) << res << "\n";
    return 0;
}

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