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
//============================================================================
// Name        : Kug.cpp
// Author      : Tytus Bierwiaczonek
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <vector>
using namespace std;

typedef unsigned int uint;

int main()
{
    const uint size = 2000;
    uint i, j, n,t;
    vector<uint> input[size];
    uint diagMins[size];
    priority_queue<uint> queue;
    unsigned long int output = 0;
    scanf("%d", &n);
//    printf("blabla\n");
    for (i = 0; i < n; ++i)
    {
        input[i] = vector<uint>(n-i);
        for (j = 0; j < n - i; ++j)
        {
            scanf("%d", &t);
            input[i][j] = t ;
//            printf("%d %d ",input[i].at(j), t);
        }
//        queues[i] = new priority_queue<uint>();
//        queues[i].push(input[i][0]);
    }
//    printf("blabla1\n");
    for (i = 1; i < n; ++i)
    {
        uint m = input[0][i];
        for (j = 1; j <= i; ++j)
        {
            m = min(input[j][i - j], m);
        }
        diagMins[i] = m;
//        printf("blabla %d\n",diagMins[i]);
    }
//    for (i = 0; i < n; ++i)
//    {
//        verticMins[i][0] = input[0][i];
//        for (j = 1; j < n - i; ++j)
//        {
//            verticMins[i][j] = min(input[j][i], verticMins[i][j - 1]);
//        }
//    }
    queue.push(input[0][0]);
    for (i = 1; i < n; ++i)
    {
        queue.push(diagMins[i-1]);
        if (input[i][0] < queue.top())
        {
            queue.pop();
            queue.push(input[i][0]);
        }
    }

    while(!queue.empty())
    {
        output += queue.top();
        queue.pop();
    }

    printf("%ld\n",output);

    return 0;
}