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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#define LL long long
#define MP make_pair
#define LIM 500
using namespace std;
bool known[2000][2000];
vector<int> from[2001];
vector<int> to[2001];
vector<pair<int, int> > newKnown;
class Info {
public:
    int value;
    int from, to;
};
bool operator< (const Info &a, const Info &b) {
    return a.value < b.value;
};
Info arr[2100000];
int n;
//int debug = 0;

void update(int a, int b) {
    from[a].push_back(b);
    to[b].push_back(a);
}

void boo(int a, int b) {
    //debug++;
    if (!known[a][b]) {
        known[a][b] = true;
        newKnown.push_back(MP(a, b));
    }
}

void handleAdd(int a, int b) {

    //right
    if (b != n - 1) {
        for (int i = 0; i < from[b + 1].size(); i++) {
            boo(a, from[b + 1][i]);
        }
    }
    //left
    if (a != 0) {
        for (int i = 0; i < to[a - 1].size(); i++) {
           boo(to[a - 1][i], b);
        }
    }
    //------------------ p2
    //right
    for (int i = 0; i < from[a].size(); i++) {
        if (from[a][i] < b) {
            boo(from[a][i] + 1, b);
        } else {
            boo(b + 1, from[a][i]);
        }
    }
    //left
    for (int i = 0; i < to[b].size(); i++) {
        if (to[b][i] > a) {
            boo(a, to[b][i] - 1);
        } else {
            boo(to[b][i], a - 1);
        }
    }
}

void start(int a, int b) {
    newKnown.clear();
    boo(a, b);
    for (int i = 0; i < newKnown.size(); i++) {
        handleAdd(newKnown[i].first, newKnown[i].second);
        if (n <= LIM) {
            update(newKnown[i].first, newKnown[i].second);
        }
    }
    if (n > LIM) {
        for (int i = 0; i < newKnown.size(); i++) {
            update(newKnown[i].first, newKnown[i].second);
        }
    }
}

int main() {
    scanf("%d", &n);
    int all = 0;
    for (int a = 0; a < n; a++) {
        for (int b = a; b < n; b++) {
            known[a][b] = false;
            scanf("%d", &arr[all].value);
            arr[all].from = a;
            arr[all].to = b;
            all++;
        }
    }
    sort(arr, arr + all);
    LL ans = 0;
    int bou = 0;
    for (int idx = 0; idx < all; idx++) {
        int a = arr[idx].from;
        int b = arr[idx].to;
        if (!known[a][b]) {
            ans += arr[idx].value;
            start(a, b);
        }
    }
    printf("%lld\n", ans);
    return 0;
}