Submission #871009

# Submission time Handle Problem Language Result Execution time Memory
871009 2023-11-09T17:12:21 Z Trisanu_Das Seesaw (JOI22_seesaw) C++17
67 / 100
2000 ms 4712 KB
#include <bits/stdc++.h> 
using namespace std;
 
int A[200005], n;
long long pref[200005];
long double ans;
 
long double calc(int l, int r) {
	return (long double)(pref[r] - pref[l - 1]) / (r - l + 1);
}
 
long double solve(long double max_r) {	
	int l = 1, r = n;
	long double tl = calc(l, r), tr = calc(l, r);
	while (l < r) {
		long double tll = min(tl, calc(l + 1, r)), tlr = max(tr, calc(l + 1, r));
		if (tlr <= max_r) l++;
		else r--;
		tl = min(tl, calc(l, r));
		tr = max(tr, calc(l, r));
		if (tr - tl >= ans) return tr - tl;
	}
	return tr - tl;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		pref[i] = pref[i - 1] + A[i];
	}
	ans = A[n] - A[1];
	for (int l = 1; l <= n; l++) for (int r = l; r <= n; r++) ans = min(ans, solve(calc(l, r)));
	cout << setprecision(10) << fixed << ans << '\n';
}

Compilation message

seesaw.cpp: In function 'long double solve(long double)':
seesaw.cpp:16:15: warning: unused variable 'tll' [-Wunused-variable]
   16 |   long double tll = min(tl, calc(l + 1, r)), tlr = max(tr, calc(l + 1, r));
      |               ^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 130 ms 2508 KB Output is correct
9 Correct 135 ms 2396 KB Output is correct
10 Correct 125 ms 2780 KB Output is correct
11 Correct 106 ms 2396 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 130 ms 2508 KB Output is correct
9 Correct 135 ms 2396 KB Output is correct
10 Correct 125 ms 2780 KB Output is correct
11 Correct 106 ms 2396 KB Output is correct
12 Execution timed out 2041 ms 4712 KB Time limit exceeded
13 Halted 0 ms 0 KB -