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
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#define scanf(args...) (scanf(args) ? : 0)
const int MAXN = 2005;
const int INF = 1e9;

int T[MAXN][MAXN];
int shortestBegin[MAXN];
int shortestEnd[MAXN];
std::pair<int, int> p[MAXN*MAXN];
bool known[MAXN][MAXN];
int rep[MAXN];
int n;

int find(int u) {
    if (rep[u] == u)
        return u;
    return rep[u] = find(rep[u]);
}

void merge(int u, int v) {
    if (u == -1 || u == INF)
        return;
    if (v == -1 || v == INF)
        return;
    //printf("lacze %d %d\n", u, v);
    rep[find(u)] = find(v);
}

void add(int a, int b) {
    if (known[a][b])
        return;

    known[a][b] = true;
    if (shortestBegin[a] != INF) {
        if (shortestBegin[a] < b)
            add(shortestBegin[a]+1, b);
        else
            add(b+1, shortestBegin[a]);
    }

    if (shortestEnd[b] != -1) {
        if (shortestEnd[b] < a)
            add(shortestEnd[b], a-1);
        else
            add(a, shortestEnd[b]-1);
    }

    shortestBegin[a] = std::min(shortestBegin[a], b);
    shortestEnd[b] = std::max(shortestEnd[b], a);
    //printf("enabling %d %d\n", a, b);
    //merge(a, b);
    /*if (b+1 < n && shortestBegin[b+1] != INF) 
        merge(a+1, shortestBegin[b+1]);
    if (a-1 >= 0 && shortestEnd[a-1] != -1)
        merge(b-1, shortestEnd[a-1]);*/
}

bool cmp(std::pair<int, int> p1, std::pair<int, int> p2) {
    return T[p1.first][p1.second] < T[p2.first][p2.second];
}

bool enabled(int a, int b) {
    /*if (a == b)
        return shortestBegin[a] == a;

    return find(a) == find(b);*/
    int pos = a;
    while (shortestBegin[pos] < b)
        pos = shortestBegin[pos]+1;

    return shortestBegin[pos] == b;
}

int main() {
    std::fill(shortestBegin, shortestBegin+MAXN, INF);
    std::fill(shortestEnd, shortestEnd+MAXN, -1);

    scanf("%d", &n);

    for (int i=0; i<n; i++)
        rep[i] = i;
    
    int size = 0;
    for (int i=0; i<n; i++)
        for (int j=i; j<n; j++) {
            scanf("%d", &T[i][j]);
            p[size++] = { i, j };
        }
    
    std::sort(p, p+size, cmp);
    long long res = 0;
    for (int i=0; i<size; i++) {
        int a = p[i].first, b = p[i].second;
        if (!enabled(a, b)) {
            //printf("=>>dodaje %d %d %d\n", a, b, T[a][b]);
            res += T[a][b];
            add(a, b);
        }
        //else
        //    printf("==>olewam %d %d\n", a, b);
    }

    printf("%Ld\n", res);
}