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
//Przemysław Jakub Kozłowski
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define FI first
#define SE second
#define MP make_pair
using namespace std;
typedef long long LL;
const int N = 2003;

void dodaj(pair<int,int> przedzial);

int n, m;
pair<int, pair<int,int> > tab[N*N];
vector<int> LEW[N], PRA[N];
int Z[N];


int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++)
    {
        for(int j = i;j <= n;j++)
        {
            int a;
            scanf("%d", &a);
            tab[++m] = MP(a, MP(i, j));
        }
    }
    //cerr << "Wczytano" << endl;
    sort(tab+1, tab+m+1);
    //cerr << "Posortowano" << endl;

    for(int i = 1;i <= n+1;i++) Z[i] = i;

    LL wyn = 0;
    for(int i = 1;i <= m;i++)
    {
        //cerr << "I: " << i << " tab[i].FI: " << tab[i].FI << " tab[i].SE: (" << tab[i].SE.FI << "," << tab[i].SE.SE << ") ";
        if(Z[tab[i].SE.FI] != Z[tab[i].SE.SE+1])
        {
            //cerr << "Dodaj ";
            wyn += tab[i].FI;
            dodaj(tab[i].SE);
        }
        /*cerr << endl;
        cerr << "LEW: ";
        for(int i = 1;i <= n;i++)
        {
            if(LEW[i].size() == 0) cerr << "X ";
            else if(LEW[i].size() == 1) cerr << LEW[i][0] << " ";
            else cerr << "BLAD ";
        }
        cerr << endl;*/
    }

    printf("%lld\n", wyn);

    return 0;
}

void dodaj(pair<int,int> przedzial)
{
    LEW[przedzial.FI].push_back(przedzial.SE);
    for(int i = 1;i <= n;i++)
        if(LEW[i].size() > 1)
        {
            if(LEW[i][0] > LEW[i][1]) swap(LEW[i][0], LEW[i][1]);
            LEW[LEW[i][0]+1].push_back(LEW[i][1]);
            LEW[i].pop_back();
        }
    for(int i = 1;i <= n;i++) PRA[i].clear();
    for(int i = 1;i <= n;i++)
        if(LEW[i].size() >= 1)
            PRA[LEW[i][0]].push_back(i);
    for(int i = n;i >= 1;i--)
        if(PRA[i].size() > 1)
        {
            if(PRA[i][0] < PRA[i][1]) swap(PRA[i][0], PRA[i][1]);
            PRA[PRA[i][0]-1].push_back(PRA[i][1]);
            PRA[i].pop_back();
        }
    for(int i = 1;i <= n;i++) LEW[i].clear();
    for(int i = 1;i <= n;i++)
        if(PRA[i].size() >= 1)
            LEW[PRA[i][0]].push_back(i);

    Z[n+1] = n+1;
    for(int i = n;i >= 1;i--)
    {
        if(LEW[i].size() == 0)
            Z[i] = i;
        else
            Z[i] = Z[LEW[i][0]+1];
    }
}