1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;

bool czy_to_sie_nie_rozjedzie(int szerokosc_fali, const vector<int>& bursztynowa_bieda, vector<int>& starty_sztormu) {
    int liczba_segmentow = (int)bursztynowa_bieda.size() - 1;
    int ile_fal_jeszcze_hula = 0;
    int ostatni_mozliwy_start = liczba_segmentow - szerokosc_fali + 1;

    for (int gdzie_plaza = 1; gdzie_plaza <= liczba_segmentow; ++gdzie_plaza) {
        if (gdzie_plaza > szerokosc_fali) {
            ile_fal_jeszcze_hula -= starty_sztormu[gdzie_plaza - szerokosc_fali];
        }

        if (gdzie_plaza <= ostatni_mozliwy_start) {
            int ile_trzeba_dopchac = bursztynowa_bieda[gdzie_plaza] - ile_fal_jeszcze_hula;
            if (ile_trzeba_dopchac < 0) return false;
            starty_sztormu[gdzie_plaza] = ile_trzeba_dopchac;
            ile_fal_jeszcze_hula += ile_trzeba_dopchac;
        } else {
            if (bursztynowa_bieda[gdzie_plaza] != ile_fal_jeszcze_hula) return false;
        }
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int liczba_segmentow;
    cin >> liczba_segmentow;

    vector<int> bursztynowa_bieda(liczba_segmentow + 1);
    long long skarbonka_bajtazara = 0;

    for (int i = 1; i <= liczba_segmentow; ++i) {
        cin >> bursztynowa_bieda[i];
        skarbonka_bajtazara += bursztynowa_bieda[i];
    }

    vector<int> kandydaci_na_rozmiar;
    for (long long dzielnik_smierdzi_podejrzanie = 1; dzielnik_smierdzi_podejrzanie * dzielnik_smierdzi_podejrzanie <= skarbonka_bajtazara; ++dzielnik_smierdzi_podejrzanie) {
        if (skarbonka_bajtazara % dzielnik_smierdzi_podejrzanie == 0) {
            if (dzielnik_smierdzi_podejrzanie <= liczba_segmentow) {
                kandydaci_na_rozmiar.push_back((int)dzielnik_smierdzi_podejrzanie);
            }
            long long drugi_delikwent = skarbonka_bajtazara / dzielnik_smierdzi_podejrzanie;
            if (drugi_delikwent != dzielnik_smierdzi_podejrzanie && drugi_delikwent <= liczba_segmentow) {
                kandydaci_na_rozmiar.push_back((int)drugi_delikwent);
            }
        }
    }

    sort(kandydaci_na_rozmiar.rbegin(), kandydaci_na_rozmiar.rend());

    vector<int> starty_sztormu(liczba_segmentow + 1);

    for (int szerokosc_fali : kandydaci_na_rozmiar) {
        if (czy_to_sie_nie_rozjedzie(szerokosc_fali, bursztynowa_bieda, starty_sztormu)) {
            cout << szerokosc_fali << '\n';
            return 0;
        }
    }

    return 0;
}