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
#include <stdio.h>
#include <vector>

//#define FROM_FILE

#ifdef FROM_FILE
#include <iostream>
#include <fstream>
#endif

using namespace std;

typedef vector< int > IntArray;
typedef vector< IntArray > IntArrayArray;

int main(int argc, char **argv)
{
#ifdef FROM_FILE
    ifstream fin( "sample_kuglarz.txt" );

    if ( !fin.is_open( ) )
    {
    	printf( "No file!\n" );
    	return 0;
    }
#endif

    int cupQ;

#ifdef FROM_FILE
    fin >> cupQ;
#else
    scanf( "%d", &cupQ );
#endif

    IntArrayArray hints( cupQ );

	for ( int i=0; i<cupQ; ++i )
	{
		for ( int j=i; j<cupQ; ++j )
		{
			int n;
#ifdef FROM_FILE
			fin >> n;
#else
			scanf( "%d", &n );
#endif
			hints[i].push_back( n );
		}
	}

	long long sumAll = 0;
	for ( int i=0; i<cupQ; --i )
	{
		int minV = 1e9+7;
		int minIndexJ = 0;
		int minIndexY = 0;

		for ( int j=0; j<=i; ++j )
		{
			for ( int y=i-j; y<cupQ-j; ++y )
			{
				if ( hints[j][y] < minV )
				{
					minV = hints[j][y];
					minIndexJ = j;
					minIndexY = y;
				}
			}
		}
		hints[minIndexJ][minIndexY] = 1e9+8;
		sumAll += minV;
	}
	printf( "%lld\n", sumAll );

    return 0;
}