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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <stdio.h>
#include <stdlib.h>

static int n, nc, a[2000][2000], b[2000], c[2000 * 1001][2], d[2000];
static long long wynik;

int porownaj(const void *e1, const void *e2)
{
    int i1 = *(int *) e1;
    int i2 = *(int *) e2;
    if (i1 < i2)
        return -1;
    else
        if (i1 == i2)
            return 0;
        else
            return 1;
}

int porownaj2(const void *e1, const void *e2)
{
    int *i1 = (int *) e1;
    int *i2 = (int *) e2;
    int por = a[i1[0]][i1[1]] - a[i2[0]][i2[1]];
    if (por < 0)
        return -1;
    else
        if (por == 0)
            return 0;
        else
            return 1;
}

void dodaj(int x, int y, int *z)
{
    int i, j, v, w;

    for (w = *z, i = x; i <= y; i++)
    {
        if (b[i] == -1)
            b[i] = w;
    }
    for (i = x; i <= y; i++)
    {
        if (b[i] < w)
        {
            v = b[i];
            (*z)++;
            b[i] = *z;
            for (j = i + 1; j <= y; j++)
                if (b[j] == v)
                    b[j] = *z;
        }
    }
}

int main()
{
    int i, j, m, w, dalej, ok;
    long long z, zm;
    scanf("%d", &n);
    for (nc = i = 0; i < n; i++)
    {
        for (j = i; j < n; j++, nc++)
        {
            scanf("%d", &a[i][j]);
            c[nc][0] = i;
            c[nc][1] = j;
        }
        b[i] = -1;
        d[i] = i;
    }
    qsort(c, nc, sizeof(int) * 2, porownaj2);
    dalej = 1;
    while (dalej)
    {
        wynik = 0;
        for (i = 0; i < n; i++)
        {
            b[i] = -1;
            wynik = wynik + a[c[d[i]][0]][c[d[i]][1]];
        }
        for (w = i = 0; i < n; i++, w++)
            dodaj(c[d[i]][0], c[d[i]][1], &w);
        qsort(b, n, sizeof(int), porownaj);
        for (ok = 1, i = 0; i < n; i++)
        {
            if (i < n - 1 && b[i] == b[i + 1])
                ok = 0;
            b[i] = -1;
        }
        if (ok)
            dalej = 0;
        else
        {
            for (m = -1, i = 0; i < n; i++)
            {
                if (i < n - 1 && d[i] + 1 < d[i + 1] || i == n - 1 && d[i] < nc - 1)
                {
                    z = (long long) a[c[d[i] + 1][0]][c[d[i] + 1][1]] - (long long) a[c[d[i]][0]][c[d[i]][1]];
                    for (j = i + 1; j < n; j++)
                        z += (long long) a[c[d[i + 1] + j - i][0]][c[d[i + 1] + j - i][1]] - (long long) a[c[d[j]][0]][c[d[j]][1]];
                    if (m == -1 || z < zm)
                    {
                        m = i;
                        zm = z;
                    }
                }
            }
            if (m >= 0)
            {
                d[m]++;
                for (i = m + 1; i < n; i++)
                    d[i] = d[m] + i - m;
            }
            else
            {
                dalej = 0;
                wynik = 0;
            }
        }
    }
    printf("%lld\n", wynik);
    return 0;
}