Submission #700839

#	Time	Username	Problem	Language	Result	Execution time	Memory
700839		m_fenais	Seesaw (JOI22_seesaw)	C++17	0 / 100	2072 ms	748 KiB

seesaw

#include <bits/stdc++.h>
#define endl '\n'
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int ll
#define all(vec) vec.begin(), vec.end()
typedef long long ll;
using namespace std;
const int N = 200 + 10, mod = 1e9 + 7;
int n;
double pref[N];
map<pair<int, int>, set<pair<double, double> > > mp;
void solve(int i, int j, int prev_i, int prev_j) {
    if(i > j) return;
    double a = double(double(pref[j] - pref[i-1])/double(j-i+1));
    for(auto it : mp[{prev_i, prev_j}]) {
        double b = min(it.first, a);
        double c = max(it.second, a);
        mp[{i, j}].insert({b, c});
    }
    solve(i, j - 1, i, j);
    solve(i + 1, j, i, j);
    return;
}
signed main()
{
    FAST;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> pref[i];
    for(int i = 2; i <= n; i++) pref[i] += pref[i-1];
    mp[{1, n}].insert({double(pref[n] / double(n)), double(pref[n] / double(n))});
    solve(1, n, 1, n);
    double ans = INT_MAX;
    for(int i = 1; i <= n; i++) {
        for(auto it : mp[{i, i}]) {
            ans = min(ans, double(abs(double(it.first) - double(it.second))));
        }
    }
    cout << fixed << setprecision(9) << ans << endl;
}

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