Submission #1176164

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

seesaw

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

using namespace std;
typedef long long ll;

vector<double> p, pref;
vector<vector<double>> dp;

double solve(double l, double r, double mn, double mx) {
    if (dp[l][r] != -1) return dp[l][r];
    double cnt = r - l;
    double sum = pref[r] - pref[l];
    double center = sum / cnt;
    
    mx = max(mx, center);
    mn = min(mn, center);

    if (cnt == 1) {
        return mx - mn;
    }
    double q1 = solve(l + 1, r, mn, mx);
    double q2 = solve(l, r - 1, mn, mx);
    return dp[l][r] = min(q1, q2);
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);

    double n;
    cin >> n;
    p.resize(n + 1, 0);
    pref.resize(n + 1, 0);
    dp.resize(n + 1, vector<double>(n + 1, -1));
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        pref[i] = pref[i - 1] + p[i];
    }
    cout << fixed << setprecision(10);
    cout << solve(0, n, 1e9, 0) << '\n';
}

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