Submission #1205392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205392		sula2	Seesaw (JOI22_seesaw)	C++20	1 / 100	2095 ms	580 KiB

seesaw

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

int a[100];
long double avg[100][100];
bool active[100][100];

bool dfs(int l, int r) {
    if (!active[l][r]) return false;
    if (l == r) return true;
    return dfs(l+1, r) | dfs(l, r-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    for (int i = 0; i < n; cin >> a[i++]);
    for (int l = 0; l < n; l++) {
        avg[l][l] = a[l];
        for (int r = l+1; r < n; r++) {
            avg[l][r] = avg[l][r-1] + a[r];
        }
        for (int r = l; r < n; r++)
            avg[l][r] /= r-l+1;
    }
    vector<tuple<int,int,double>> nodes;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            nodes.emplace_back(l, r, avg[l][r]);
        }
    }
    sort(all(nodes), [&](tuple<int,int,double> a, tuple<int,int,double> b) {
        return get<2>(a) < get<2>(b);
    });
    int r = 0;
    double ans = 1e9;
    for (int l = 0; l < nodes.size(); l++) {
        {
//            auto [x, y, z] = nodes[l];
//            cout<<x<<' '<<y<<' '<<z<<'\n';
        }
        while (r < nodes.size() && !dfs(0, n-1)) {
            auto [x, y, z] = nodes[r++];
            active[x][y] = true;
        }
        if (dfs(0, n-1)) {
            auto [b, c, d] = nodes[l];
            auto [e, f, g] = nodes[r-1];
            ans = min(ans, g - d);
        }
        auto [x, y, z] = nodes[l];
        active[x][y] = false;
    }
    cout << fixed << setprecision(10) << ans;
}

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