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
92
93
94
95
#include <iostream>
#include <vector>

using namespace std;

struct DaneMinimum{
    long int wartosc;
    int pozycja;
};

long int spr_min( vector<long int> tab, int p );

int main(){
    ios_base::sync_with_stdio(0);

    short n;
    cin>>n;

    vector<long int> *tab = new vector<long int>[n];
    DaneMinimum *tMinimum = new DaneMinimum[n];
    long int *tSumy = new long int [n];
    DaneMinimum najmniejszaSuma;
    najmniejszaSuma.wartosc = 1000000000;

    for( int i = 0; i < n; ++i ){
        DaneMinimum minimum;
        minimum.wartosc = 1000000000;
        long int suma = 0;

        for( int j = 0; j < n - i; ++j ){
            long int x;
            cin>>x;

            if( minimum.wartosc > x ){
                minimum.wartosc = x;
                minimum.pozycja = j;
            }

            suma += x;
            tab[i].push_back(x);
        }

        if( najmniejszaSuma.wartosc > suma ){
            najmniejszaSuma.wartosc = suma;
            najmniejszaSuma.pozycja = i;
        }

        tSumy[i] = suma;
        tMinimum[i] = minimum;
    }
    int stopien = n - najmniejszaSuma.pozycja;
    int od;
    long int wynik = najmniejszaSuma.wartosc;

    while( n != stopien ){
        od = najmniejszaSuma.pozycja;
        najmniejszaSuma.wartosc = tMinimum[od-1].wartosc;
        najmniejszaSuma.pozycja = od-1;
        int licz = 2;

        for( int i = n - 1 - stopien; i > 0; --i ){
            long int spr = spr_min( tab[i-1], licz++ );
            if( najmniejszaSuma.wartosc >= spr ){
                najmniejszaSuma.wartosc = spr;
                najmniejszaSuma.pozycja = i-1;
            }
        }
        stopien += od - najmniejszaSuma.pozycja;
        wynik += najmniejszaSuma.wartosc;
    }

    cout<<wynik<<endl;
}
long int spr_min( vector<long int> tab, int p ){
    long int minimum = 0;

    for( int i = 0; i < p; ++i ){
        minimum += tab[i];
    }

    for( vector<long int>::iterator i = tab.begin()+1; i != tab.end()- (p-1); ++i ){
        long int suma = 0;

        for( vector<long int>::iterator j = i; j != i+p; ++j ){
            suma += *j;
        }

        if( minimum > suma ){
            minimum = suma;
        }
    }

    return minimum;

}