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
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int i, n, c, wynik=1, pierwiastek, j, ok, ile_fal, brakuje;
    long long suma=0;
    cin >> n;
    vector<int> bursztyny(n), dzielniki, fale(n+1);
    for(i=0; i<n; i++) {
        cin >> bursztyny[i];
        suma+=bursztyny[i];
    }
    pierwiastek=sqrt(suma);
    for(i=1; i<=pierwiastek; i++) {
        if(suma%i==0) {
            dzielniki.push_back(i);
            if(i*i!=suma)
                dzielniki.push_back(suma/i);
        }
    }
    sort(dzielniki.rbegin(), dzielniki.rend());
    for(j=0; j<dzielniki.size(); j++) {
        c=dzielniki[j];
        if(c>n)
            continue;
        for(i=0; i<=n; i++)
            fale[i]=0;
        ile_fal=0;
        ok=1;
        for(i=0; i<n; i++) {
            ile_fal+=fale[i];            
            if(ile_fal>bursztyny[i]) {
                ok=0;
                break;
            }            
            brakuje=bursztyny[i]-ile_fal;
            if(brakuje>0) {
                if(i+c>n) {
                    ok=0;
                    break;
                }
                ile_fal+=brakuje;
                fale[i+c]-=brakuje;
            }
        }
        if(ok) {
            wynik=c;
            break;
        }
    }
    cout << wynik;
}