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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <deque>
#include <bitset>

#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 

using namespace std;

struct query {
    int x, y;
    long long cost;
    bool operator<(const query& q) const {
        if (cost != q.cost) return cost < q.cost;
        if (x != q.x) return x < q.x;
        return y < q.y;
    }
};

const int MAX_M = 2010 * 2010 / 2;
const int MAX_N = 2010;
int n;
query d[MAX_M];

struct my_bitset {
    vector<unsigned long long> s;

    void resize(int size) {
        s.resize(size/64 + 1, 0ull);
    }

    void set(int pos) {
        s[pos/64] |= (1ull << (pos % 64));
    }

    void operator|=(const my_bitset& x) {
        REP(i, s.size()) s[i] |= x.s[i];
    }

    bool get(int pos) {
        return s[pos/64] & (1ull << (pos % 64));
    }
};

struct sit {
    vector<int> s, os;
    sit() : s(n+10, -1), os(n+10, -1) {
        REP(i, n) c[i].resize(n);
    }
    
    bool makes_sense(query& q) {
        return !c[q.y].get(q.x);
    }

    bool makes_sense2(query& q) {
        int x = q.x;
        while (x <= q.y) {
            if (s[x] == -1) return true;
            x = s[x] + 1;
            if (x == q.y+1) return false;
        }
        return true;
    }

    void add(query& q) {
        deque<pair<int, int> > w;
        w.push_back(make_pair(q.x, q.y));

        while (!w.empty()) {
            int x = w[0].first;
            int y = w[0].second;
            w.pop_front();
//            printf("loop dla %d %d\n", x, y);

            if (s[x] == -1 and os[y] == -1) {
                // Zupelnie nowy
                s[x] = y;
                os[y] = x;
            } else if (s[x] != -1) {
                // Obetnij z prawej
                w.push_back(make_pair(x, min(y, s[x])));
                w.push_back(make_pair(min(y, s[x])+1, max(y, s[x])));
                os[s[x]] = -1;
                s[x] = -1;
              } else {
                w.push_back(make_pair(max(x, os[y]), y));
                w.push_back(make_pair(min(x, os[y]), max(x, os[y])-1));
                s[os[y]] = -1;
                os[y] = -1;
            }
        }
    }

    void print() {
        printf("s:"); REP(i, n) printf(" %d", s[i]); printf("\n");
        printf("os:"); REP(i, n) printf(" %d", os[i]); printf("\n");
    }

    my_bitset c[MAX_N];
    void fix() {
        REP(i, n) {
            if (os[i] != -1) c[i].set(os[i]);
            if (s[i+1] != -1) c[s[i+1]] |= c[i];
        }
    }

};

int main() {
    scanf("%d", &n);
    int m = n*(n+1) / 2;
    int cnt = 0;
    REP(i, n) FOR(j, i, n) {
        d[cnt].x = i;
        d[cnt].y = j;
        scanf("%lld", &d[cnt].cost);
        ++cnt;
    }
    sort(d, d+m);

    sit s;
    int count = 0;
    long long cost = 0;
    REP(i, m) {
        if (!s.makes_sense(d[i])) continue;
//        printf("dodaje %d %d %lld\n", d[i].x, d[i].y, d[i].cost);
        s.add(d[i]);
//        s.print();
        cost += d[i].cost;
        if (++count >= n) break;
        s.fix();
    }

    printf("%lld\n", cost);
    return 0;
}