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

int main(void) {
	
	unsigned short int n,i, j, t;

	scanf("%hu", &n);

	unsigned long int prices[n][n]; 
    unsigned short int known[n];
    unsigned long long int lowestPrice = 0;
    
	for (i=0;i<n;i++)
	{
		for (j=0;j<(n-i);j++)
			scanf("%lu", &prices[i][j]);

		known[i] = 0;
	}
	
	
	for (t=0;t<n;t++)
	{
		unsigned long int best_pos = -1, best_price = 0;
		
		for (i=0;i<n;i++)
		{
			j=0;
			
			unsigned long int cup_pos = -1, cup_price = 0, unknown_so_far = 0;
	
			while(j<(n-i) && unknown_so_far < 2)
			{
				int pos = j + i;
	
				if(known[pos] == 0 && cup_pos == -1) //cup position
				{
					cup_pos = pos;
					cup_price = prices[i][j];
					unknown_so_far += 1;
				}
				
				else if(known[pos] == 0 && cup_pos != -1) // stop searching if encountered second unknown
					unknown_so_far += 1;
					
				else if(known[pos] == 1 && cup_pos != -1) // handle lowest price
				{
					if(prices[i][j] < cup_price)
						cup_price = prices[i][j];
				}
				j += 1;
			}
			
			if(best_pos == -1) //set initial best position
			{
				
				best_pos = cup_pos;
				best_price = cup_price;
				
			}
			else if(cup_pos != -1 && best_price > cup_price) //update best choice position
			{
				best_pos = cup_pos;
				best_price = cup_price;
			}
			
		}
		known[best_pos] = 1;
		lowestPrice += best_price;
	}
	printf("%lld", lowestPrice);
	return 0;
}