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
#include <iostream>

using namespace std;

long long a[100005];
long long w[100005];

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

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

    long long total_sum = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        total_sum += a[i];
    }
    
    a[0] = 0;
    a[n + 1] = 0;

    for (int k = n; k >= 1; --k) {
        if (total_sum % k != 0) continue;

        long long target = total_sum / k;
        bool sum_ok = true;

        for (int r = 1; r <= k; ++r) {
            long long current_sum = 0;
            for (int i = r; i <= n; i += k) {
                current_sum += a[i];
            }
            if (current_sum != target) {
                sum_ok = false;
                break;
            }
        }

        if (!sum_ok) continue;

        bool possible = true;
        for (int i = 1; i <= n + 1; ++i) {
            w[i] = a[i] - a[i - 1];
            if (i > k) {
                w[i] += w[i - k];
            }
            if (w[i] < 0) {
                possible = false;
                break;
            }
        }

        if (possible) {
            cout << k << "\n";
            return 0;
        }
    }

    return 0;
}