Submission #1205400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205400		sula2	Seesaw (JOI22_seesaw)	C++20	34 / 100	40 ms	652 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], n;
long double avg[100][100];
bool active[100][100], reachable[100][100];

bool dfs() {
    for (int l = 0; l < n; l++)
        reachable[l][l] = active[l][l];
    for (int len = 2; len <= n; len++) {
        for (int l = 0, r = len-1; r < n; l++, r++) {
            reachable[l][r] = active[l][r] & (reachable[l+1][r] | reachable[l][r-1]);
        }
    }
    return reachable[0][n-1];
}

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

    cin >> n;
    for (int i = 0; i < n; cin >> a[i++]);
//    for (int i = 0; i < n; a[i++] = 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++) {
        while (r < nodes.size() && !dfs()) {
            auto [x, y, z] = nodes[r++];
            active[x][y] = true;
        }
        if (dfs()) {
            auto [b, c, d] = nodes[l];
            auto [e, f, g] = nodes[r-1];
//            printf("%d %d %d %d", b, c, e, f);
            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: 33 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33