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
#include <cstdio>
#include<vector>
#include <algorithm>
#include <set>
#define PB push_back
#define MP make_pair
using namespace std;
struct przed {
int od, dok, w;
};
przed mPrzed(int a, int b, int c)
{
przed p;
p.od=a;
p.dok=b;
p.w=c;
return p;
}

bool por(przed a, przed b)
{
	if(a.w<b.w)
	return true;
	if(a.w>b.w)
		return false;
	if(a.od<b.od)
		return true;
	if(a.od>b.od)
		return true;
	return (a.dok<b.dok);
		
}

vector<przed> prz;

int n, ileNieznane, ileBrzegow;
long long wyn;
const int N=2005;
bool znane[N];
bool zajete[N];
bool uzyte[N*N];
int gdzie(int a)
{
return a;
}

void usunNajmniejszy()
{
	
}

void dodaj(przed a)
{}
int main()
{
scanf("%d", &n);
ileNieznane=n;
for (int i=1; i<=n; i++)
{
	for (int j=0; j<n-i+1; j++)
	{
	int a;
	scanf("%d", &a);
	prz.PB(mPrzed(i, i+j, a));
	}
}
sort(prz.begin(), prz.end(), por);
bool czy;
	ileBrzegow=0;
	for(int i=0; i<prz.size()&&ileBrzegow<(ileNieznane+1); i++)
	{
	przed pom = prz[i];
	czy=false;
	//printf("%d %d %d %d %d\n", pom.od, pom.dok, pom.w, zajete[gdzie(pom.od)], zajete[gdzie(pom.dok)]);
		if (!zajete[gdzie(pom.od)])
		{
			ileBrzegow++;
			zajete[gdzie(pom.od)]=true;
			uzyte[i]=true;
			czy=true;
		}
		if (!zajete[gdzie(pom.dok)+1])
		{
			ileBrzegow++;
			zajete[gdzie(pom.dok)+1]=true;
			uzyte[i]=true;
			czy=true;
		}
		if (czy)
		{
			wyn+=pom.w;
			dodaj(pom);
			//printf("P%d\n", pom.w);
		}
	}
	int k=0;
	while (ileBrzegow<(ileNieznane+1))
	{
		if (!uzyte[k])
		{
			wyn+=prz[k].w;
			//printf("K%d\n", prz[k].w);
			ileBrzegow++;
		}
		k++;
	}
printf("%lld\n", wyn);
return 0;
}