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

typedef long long ll;
const int MAXN = 2005;
//ll cost[MAXN][MAXN];
//ll sol[MAXN][MAXN];
bool cancelled[MAXN][MAXN];

struct interval {
  int a, b;
  ll cost;
};
interval intervals[MAXN*MAXN];

bool operator<(interval i1, interval i2) {
//  printf("%d-%d:%lld < %d-%d: %lld = %d\n", i1.a, i1.b, i1.cost, i2.a, i2.b, i2.cost, i1.cost < i2.cost);
  return i1.cost < i2.cost;
}

set< pair< int, int > > cancelledSet;


int main() {
  int n;

  scanf("%d", &n);

  ll cost;
  int intervalsCount = 0;
  for(int i = 0; i < n; i++) {
    for(int j = i; j < n; j++) {
      scanf("%lld", &cost);
      intervals[intervalsCount].a = i;
      intervals[intervalsCount].b = j;
      intervals[intervalsCount].cost = cost;
      intervalsCount++;
    }
  }

  sort(intervals, intervals+intervalsCount);
//  for(int i = 0; i < intervalsCount; i++) {
//    printf("%d-%d: %lld\n", intervals[i].a, intervals[i].b, intervals[i].cost);
//  }

  ll result = 0;
  int takenCount = 0;
  for(int i = 0; i < intervalsCount && takenCount < n; i++) {
    interval& currIn = intervals[i];
    if(cancelled[currIn.a][currIn.b] == 0) {
//      printf("Taking %d-%d: %lld\n", currIn.a, currIn.b, currIn.cost);
      result += currIn.cost;
//      printf("new_result: %lld\n", result);
      takenCount++;
      vector< pair< int, int> > newCanc;
      for(set< pair< int, int> >::iterator it = cancelledSet.begin(); it != cancelledSet.end(); it++) {
        if(it->second < currIn.a-1) {
          newCanc.push_back(make_pair(it->second+1, currIn.a-1));
        }
        else if(it->first > currIn.b+1) {
          newCanc.push_back(make_pair(currIn.b+1, it->first-1));
        }

        if(it->second == currIn.a-1) {
          newCanc.push_back(make_pair(it->first, currIn.b));
        }
        else if(it->first == currIn.b+1) {
          newCanc.push_back(make_pair(currIn.a, it->second));
        }

        if(it->first == currIn.a) {
          if(it->second > currIn.b) {
            newCanc.push_back(make_pair(currIn.b+1, it->second));
          } else {
            newCanc.push_back(make_pair(it->second+1, currIn.b));
          }
        }

        if(it->second == currIn.b) {
          if(it->first < currIn.a) {
            newCanc.push_back(make_pair(it->first, currIn.a-1));
          } else {
            newCanc.push_back(make_pair(currIn.a, it->second));
          }
        }
      }

      for(vector< pair< int, int> >::iterator it = newCanc.begin(); it != newCanc.end(); it++) {
        cancelledSet.insert(*it);
//        printf("cancelling: %d-%d\n", it->first, it->second);
        cancelled[it->first][it->second] = 1;
      }
      cancelledSet.insert(make_pair(currIn.a, currIn.b));
      cancelled[currIn.a][currIn.b] = 1;
//      printf("cancelling: %d-%d\n", currIn.a, currIn.b);
      cancelled[currIn.a][currIn.b] = 1;
    }
  }

  printf("%lld\n", result);

  return 0;
}