Submission #1073737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073737		prvocislo	Seesaw (JOI22_seesaw)	C++17	67 / 100	2101 ms	5380 KiB

seesaw

// I was grinning like I'm winning, I was hitting my marks
// 'Cause I can do it with a broken heart 
// 1 2 3 4 ...

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <bitset>
typedef long long ll;
typedef long double ld;
using namespace std;

vector<ll> a, pf;

ld avg(int l, int r) { return (ld)(pf[r + 1] - pf[l]) / (ld)(r - l + 1); }

void chmax(ld& a, ld b) { a = max(a, b); }
void chmin(ld& a, ld b) { a = min(a, b); }

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	a.assign(n, 0), pf.assign(n + 1, 0);
	for (int i = 0; i < n; i++) cin >> a[i], pf[i + 1] = pf[i] + a[i];
	ld ans = a[n - 1];
	for (int l = 0; l < n; l++) for (int r = l; r < n; r++)
	{
		ld c = avg(l, r);
		ld mi = avg(0, n - 1);
		ld mx = avg(0, n - 1);
		if (c > mi || mi - c > ans) continue;
		int li = 0, ri = n - 1;
		while (li < ri)
		{
			if (avg(li, ri - 1) >= c) ri--;
			else li++;
			chmin(mi, avg(li, ri));
			chmax(mx, avg(li, ri));
			if (mx - mi > ans) break;
		}
		chmin(ans, mx - mi);
	}
	cout << setprecision(9) << fixed;
	cout << ans << "\n";
	return 0;
}

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