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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
#define ll long long
#define ld long double
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define mini(a,b) a=min(a,(b))
#define maxi(a,b) a=max(a,(b))
#define RE(i,n) for(int i=0,_n=(n);i<_n;++i)
#define RI(i,n) for(int i=1,_n=(n);i<=_n;++i)
const int inf=1e9+5, nax=2e3+5;

vector<pair<int, pii > > wp;
int n;
bool t[nax][nax];
vector<pii > kol;
int start[nax], koniec[nax];

void dodaj(int a, int b)
{
	if(a < 1 || b > n || t[a][b]) return;
	kol.pb(mp(a, b));
	t[a][b] = true;
}

void dodaj_main(int a, int b)
{	
	if(b + 1 <= start[a]) dodaj(b + 1, start[a]);
	else dodaj(start[a] + 1, b);
	
	if(a <= koniec[b] - 1) dodaj(a, koniec[b] - 1);
	else dodaj(koniec[b], a - 1);
	
	dodaj(a, start[b + 1]);
	dodaj(koniec[a - 1], b);
}

int main()
{
	scanf("%d", &n);
	RE(i, n + 3) start[i] = inf;
	RI(i, n) for(int j = i; j <= n; ++j) {
		int a;
		scanf("%d", &a);
		wp.pb(mp(a, mp(i, j)));
	}
	RI(i, n) RI(j, n) t[i][j] = false;
	sort(wp.begin(), wp.end());
	ll RES = 0;
	RE(i, wp.size())
		if(!t[wp[i].nd.st][wp[i].nd.nd]) {
			RES += (ll) wp[i].st;
			dodaj(wp[i].nd.st, wp[i].nd.nd);
			for(int j = 0; j < (int) kol.size(); ++j)
				dodaj_main(kol[j].first, kol[j].second);
			
			RE(j, kol.size()) {
				mini(start[kol[j].st], kol[j].nd);
				maxi(koniec[kol[j].nd], kol[j].st);
			}
			kol.clear();
		}
	printf("%lld", RES);
	return 0;
}