Official Analysis (C++)

Explanation

We can binary search on real values to find the minimum average $X$ we can achieve.

Now, if we find the prefix sum array $\texttt{pref}$ of the machine milk production array $M$, consider the condition we need to achieve an average $\le X$ by removing the subarray $(i, j]$:

where $S$ is the current sum of the array. After multiplying both sides by the denominator and isolating all terms involving $i$, we get:

For a fixed $j$, we should try to minimize the left side expression. So we can iterate $j$ from $2$ to $N - 1$ and keep a running minimum of the left side of the inequality. If the condition is satisfied, we can achieve an average $\le X$.

Implementation

Time Complexity: $\mathcal{O}(N\log\left(\frac{1}{\varepsilon}\right))$, where $\varepsilon$ is the fixed error margin.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("sabotage.in", "r", stdin);
	freopen("sabotage.out", "w", stdout);

	int n;
	cin >> n;
	vector<int> m(n);

Copy
with open("sabotage.in", "r") as read:
	n = int(read.readline())
	m = [int(read.readline()) for i in range(n)]

pref_sum = [0]
for i in range(n):
	pref_sum.append(pref_sum[-1] + m[i])
arr_sum = sum(m)