oj.uz

Submission #802256

# Submission time Handle Problem Language Result Execution time Memory
802256 2023-08-02T11:19:07 Z Sohsoh84 Seesaw (JOI22_seesaw) C++17
67 / 100
 2000 ms 4564 KB 
// Wounds should become scars but I'm cracked instead U+1FAE0
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;

int A[MAXN], n;
ll ps[MAXN];
ld ans;

inline ld calc(int l, int r) {

	return ld(ps[r] - ps[l - 1]) / (r - l + 1);
}

inline ld solve(ld max_r) {	
	int l = 1, r = n;
	ld tl = calc(l, r), tr = calc(l, r);
	while (l < r) {
		ld 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); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		ps[i] = ps[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 << endl;
	return 0;
}

Compilation message

seesaw.cpp: In function 'ld solve(ld)':
seesaw.cpp:32:6: warning: unused variable 'tll' [-Wunused-variable]
   32 |   ld tll = min(tl, calc(l + 1, r)), tlr = max(tr, calc(l + 1, r));
      |      ^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 116 ms 360 KB Output is correct
9 Correct 116 ms 356 KB Output is correct
10 Correct 130 ms 340 KB Output is correct
11 Correct 96 ms 356 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 116 ms 360 KB Output is correct
9 Correct 116 ms 356 KB Output is correct
10 Correct 130 ms 340 KB Output is correct
11 Correct 96 ms 356 KB Output is correct
12 Execution timed out 2037 ms 4564 KB Time limit exceeded
13 Halted 0 ms 0 KB -