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

struct prze
{
int p,k,w;
};

prze twe[2000009];
bool tb[2001][2001];

bool comp(prze a, prze b)
{
if(a.w<b.w) return true; else return false;
}

int min(int a, int b)
{
if (a<b) return a; else return b;
}

int max (int a, int b)
{
if (a>b) return a; else return b;
}

void spr(int a, int b)
{
if(twe[a].p==twe[b].p)
{
	tb[min(twe[a].k,twe[b].k)+1][max(twe[a].k,twe[b].k)]=true;
}
else if (twe[a].k==twe[b].k)
{
	tb[min(twe[a].p,twe[b].p)][max(twe[a].p,twe[b].p)-1]=true;
}
}



int main()
{
long long int wyn=0;
int n,l=0,p=0;
scanf("%d",&n);
for (int i=0;i<n;i++)
	for (int j=i;j<n;j++)
	{
		scanf("%d",&twe[l].w);
		twe[l].p=i+1;
		twe[l].k=j+1;
		l++;
	}
sort(twe,twe+l,comp);
for (int i=0;i<l;i++)
	if(!tb[twe[i].p][twe[i].k])
	{
		wyn+=twe[i].w;
		for (int j=0;j<i;j++) spr(i,j);
		p++;
				//printf("%d %d %d\n",twe[i].p,twe[i].k,twe[i].w);
		if(p==n) break;
	}
printf("%lld",wyn);
return 0;
}