Tutorial for Codeforces 1358E - Are You Fired?

Solution #

First, let’s define the function $f_k(i)=a_i+a_{i+1}+\dots +a_{i+k-1}$, i.e. the sum of $k$ consecutive months starting at $i$.

Now, let’s prove that if $k$ is one answer and $k\leq \dfrac n 2$, then $2\cdot k$ is also an answer: $f_{2k}(i)=f_k(i)+f_k(i+k)>0$. Thus we can always find an answer greater than $\dfrac n 2$.

Then, consider the case where $x\ge 0$. If $k$ is an answer, since $f_{k+1}(i)=f_k(i)+a_{i+1}=f_k(i)+x>0$, $k+1$ is also an answer. Thus it’s sufficient to check if $k=n$ is the answer.

Lastly, when $x<0$, we need the help of the prefix sum. Define $pre_i=a_0+a_1+\dots+a_{i-1},i>0$ and $pre_0=0$. We want to find a $k$ such that for each $0\leq i\leq n-k$, we have:

Since $k>\dfrac n 2$, the numbers after the window must be $x$, so the formula can be rewrite as:

For each $i$, the corresponding $k$ is $n-i$, this means if the max value of the LHS is smaller than $pre_n+x\cdot (n-i)$, then $k=n-i$ is a answer.

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    forn(i, (n + 1) / 2) {
        cin >> a[i];
    }
    int x;
    cin >> x;
    for (int i = (n + 1) / 2; i < n; i++) a[i] = x;
    vector<ll> ps(n + 1);
    partial_sum(all(a), ps.begin() + 1);
    if (ps.back() > 0) return cout << n, 0;
    if (x >= 0) return cout << -1, 0;
    ll N2 = n / 2, N1 = n - N2, sum = ps.back();
    ll mx = -1e18;
    for (int i = 0; i <= N1; i++) {
        mx = max(mx, ps[i] + x * ll(n - i));
        if (mx < sum + x * ll(n - i)) {
            cout << n - i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}