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
#include<stdio.h>
#include<set>
#include<algorithm>
using namespace std;


struct interval {
    int a,b;
    long long int c;
};

const bool cmp(const interval &x, const interval &y) {
    if(x.c == y.c)
        return x.b - x.a < y.b - y.a;
    return x.c < y.c;
}

set<int> start[2010];
set<int> finish[2010];

interval T[4010000];

int n,q,k;
int x,y;
long long int cost = 0;

int main() {
    scanf("%d", &n);
    q = 0;
    k = 0;
    for(int i=1;i<=n;i++) {
        for(int j=i;j<=n;j++) {
            scanf("%lld", &T[q].c);
            T[q].a = i;
            T[q].b = j;
            q++;
        }
    }
    sort(T, T+q, cmp);
/*
    for(int i=0;i<3000;i++)
        printf("%d %d -> %lld\n", T[i].a, T[i].b, T[i].c);
*/
    for(int i=0; i<q && k<n; i++) {
        x = T[i].a;
        y = T[i].b;
        bool exists = ( finish[x].find(y) != finish[x].end() );
        if(exists) continue;

        for(auto b : finish[y+1]) {
            if(finish[x].find(b) != finish[x].end()) {
                exists = true;
                break;
            }
        }
        if(exists) continue;
    
        for(auto b : start[x-1]) {
            if(finish[b].find(y) != finish[b].end()) {
                exists = true;
                break;
            }
        }
        if(exists) continue;

        for(auto b : start[x-1]) {
            for(auto bb : finish[y+1]) {
                if(finish[b].find(bb) != finish[b].end()) {
                    exists = true;
                    break;
                }
            }
            if(exists) break;
        }
        if(exists) continue;

        cost = cost + T[i].c;
        k++;
        finish[x].insert(y);
        start[y].insert(x);

        for(auto b : finish[y+1]) {
            finish[x].insert(b);
            start[b].insert(x);
        }

        for(auto b : start[x-1]) {
            finish[b].insert(y);
            start[y].insert(b);
        }
        
        for(auto b : start[x-1]) {
            for(auto bb : finish[y+1]) {
                finish[b].insert(bb);
                start[bb].insert(b);
            }
        }
    }
    printf("%lld\n", cost);

    return 0;
}