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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

class BajtockaPlaza {

    int segmentsCount;
    vector<long long> amberCounts;
    long long totalAmbers;

    bool aSzerokaTaFala(int waveWidth) {
        vector<long long> diffArray(segmentsCount + 2, 0);

        diffArray[1] = amberCounts[1];
        for (int index = 2; index <= segmentsCount; ++index) {
            diffArray[index] = amberCounts[index] - amberCounts[index - 1];
        }
        diffArray[segmentsCount + 1] = -amberCounts[segmentsCount];

        for (int index = 1; index <= segmentsCount; ++index) {
            if (diffArray[index] < 0) {
                return false;
            }
            if (diffArray[index] > 0) {
                if (index + waveWidth > segmentsCount + 1) {
                    return false;
                }
                diffArray[index + waveWidth] += diffArray[index];
            }
        }

        return diffArray[segmentsCount + 1] == 0;
    }

public:
    BajtockaPlaza(int segmentsCount, const vector<long long>& amberCounts, long long totalAmbers)
        : segmentsCount(segmentsCount), amberCounts(amberCounts), totalAmbers(totalAmbers) {}

    int aWysokaTaFala() {
        vector<int> candidates;

        for (long long divisor = 1; divisor * divisor <= totalAmbers; ++divisor) {
            if (totalAmbers % divisor == 0) {
                if (divisor <= segmentsCount) {
                    candidates.push_back(divisor);
                }
                long long otherDivisor = totalAmbers / divisor;
                if (otherDivisor <= segmentsCount && otherDivisor != divisor) {
                    candidates.push_back(otherDivisor);
                }
            }
        }

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

        for (int waveWidth : candidates) {
            if (aSzerokaTaFala(waveWidth)) {
                return waveWidth;
            }
        }

        return 1;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int elementsCount;
    if (!(cin >> elementsCount)) return 0;

    vector<long long> inputAmbers(elementsCount + 1, 0);
    long long inputTotalSum = 0;

    for (int index = 1; index <= elementsCount; ++index) {
        cin >> inputAmbers[index];
        inputTotalSum += inputAmbers[index];
    }

    BajtockaPlaza rozwiazywaczBajtockiejPlazy(elementsCount, inputAmbers, inputTotalSum);

    int maxWaveWidth = rozwiazywaczBajtockiejPlazy.aWysokaTaFala();

    cout << maxWaveWidth << endl;

    return 0;
}