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

int main(void){
    int n;
    scanf("%d", &n);
    int c[2000][2000];
    for (int i=0; i<n; i++)
        for (int j=i; j<n; j++)
            scanf("%d", &(c[i][j]));
    int *ww = new int [n];
    for (int i=0; i<n; i++)
        ww[i]=c[i][i];
    for (int i=1; i<n; i++)
    {
        //sprawdzamy kawalki o dl i+1
        for (int j=0; j<n-i; j++)
        {
            int max = ww[j];
            int maxk = 0;
            for (int k=1; k<i+1; k++)
                if (ww[j+k]>max)
                {
                    max = ww[j+k];
                    maxk=k;
                }
            if (max>c[j][j+i])
                ww[j+maxk]=c[j][j+i];
        }
    }
    int sum=0;
    for (int i=0; i<n; i++)
        sum+=ww[i];
    printf("%d\n",sum);
    delete [] ww;
    return 0;
}