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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <math.h>
#include <set>
#include <algorithm>
#include <vector>
#include <string.h>
#define For(i, n) for (int i = 0; i < (n); i++)
#define ForD(i, n) for (int i = (n) - 1; i >= 0; i--)
#define in cin>>
#define out cout<<
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
using namespace std;
typedef long long LL;

const int N = 2001;

struct interval
{
	pair <int, int> cord;
	int cost;

	interval(bool _read = false)
	{
		if (_read)
			read();
		else
			cost = 0,
			cord = mp(0, 0);
	}

	inline void read()
	{
		in cost;
	}

	inline bool operator< (interval other)
	{
		return cost < other.cost;
	}
};

set <pair <int, int> > A[N];

void AddIntervals(pair <int, int> inv)
{
	if (A[inv.first].find(inv) != A[inv.first].end())
		return;

	A[inv.first].insert(inv);
	A[inv.second].insert(inv);

	for (set <pair <int, int> >::iterator it = A[inv.first].begin(); it != A[inv.first].end(); it++)
		if ((*it).second < inv.second && (*it).first == inv.first)
			AddIntervals(make_pair((*it).second, inv.second));
		else if ((*it).second > inv.second && (*it).first == inv.first)
			AddIntervals(make_pair(inv.second, (*it).second));
		else if ((*it).second == inv.first)
			AddIntervals(make_pair((*it).first, inv.second));

	for (set <pair <int, int> >::iterator it = A[inv.second].begin(); it != A[inv.second].end(); it++)
		if ((*it).first < inv.first && (*it).second == inv.second)
			AddIntervals(make_pair((*it).first, inv.first));
		else if ((*it).first > inv.first && (*it).second == inv.second)
			AddIntervals(make_pair(inv.first, (*it).first));
		else if ((*it).first == inv.second)
			AddIntervals(make_pair(inv.first, (*it).second));
}

inline bool IsUnique(interval & inv)
{
	int beg = inv.cord.first;
	int end = inv.cord.second;

	if (A[beg].find(inv.cord) != A[beg].end())
		return false;
	AddIntervals(inv.cord);
	
	return true;
}

inline bool cmp(interval lhs, interval rhs)
{
	return lhs.cost < rhs.cost;
}

int main()
{
	ios_base::sync_with_stdio();
	
	int n;
	in n;

	vector <interval> data;
	For (i, n)
		For (j, n - i)
		{
			interval inv(true);
			inv.cord.ft = i;
			inv.cord.sd = j + i + 1;
			data.push_back(inv);
		}

	sort(data.begin(), data.end(), cmp);
	LL Res = 0;
	int cnt = 0;
	
	For (i, data.size())
	{
		if (IsUnique(data[i])) {
			Res += data[i].cost,
			cnt++;
		}

		if (cnt == n)
			break;
	}
	
	out Res;

	//system("pause");
	return 0;
}