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
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;


class polaczenie
{public:
    int i,j;
    int koszt;
    bool operator < (const polaczenie& other ) const {return koszt<other.koszt;}
    polaczenie (int ii,int jj,int k):i(ii),j(jj),koszt(k){}
};


int main()
{

    int n;
    cin.sync_with_stdio(false);

    cin>>n;

    /* generator zośliwego przypadku
    cout<<n<<endl;
    for (int i=1;i<=n;i++)
    {
        //if (i<n) cout<<"1 ";
        for(int j=i;j<=n-1;j++)
        {
            cout<<j-i<<" ";
        }
        cout<<2*n<<" "<<endl;
    }
    return 0;*/


    vector <polaczenie> polaczenia;
    polaczenia.reserve((n+2)*(n+2)/2);

    for (int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            int c;
            cin>>c;
        //    C[i][j]=c;
            polaczenia.emplace_back(i,j,c);
        }


    sort(polaczenia.begin(),polaczenia.end());

    vector<int> konce(n+1,0);  // koniec[i]=j oznacza belkę i-j.

    int wymiar=0;
    int index=0;
    int64_t koszt=0;
    while (wymiar<n)
    {
        polaczenie belka = polaczenia[index];
        index++;

        while ( konce[belka.i]!=0 )
        {
            if (konce[belka.i]==belka.j)
            {
             //   cout<<"jest"<<endl;
                belka.i=0;
                break;
            }

            int M,m;
            if (konce[belka.i]>belka.j)
            {
                M=konce[belka.i];
                m=belka.j;
            }else
            {
                m=konce[belka.i];
                M=belka.j;
            }

            //heurystyka walczaca z O(n^3)
            //chcemy, aby belka bazowa zajmowałą z grubsza
            //polowę miejsca miedzy swoim początkiem a końcem.
            if ( abs(M-(belka.i+n/2))<abs(m-(belka.i+n/2) ) )
                 konce[belka.i]=M;
            else
                 konce[belka.i]=m;
            //nie wiemy jeszcze, czy belka wejdzie do bazy, ale
            //jeśli nie wejdzie, tzn była liniiowo zależna od bazy
            // - mamy prawo ją odjąć.


            belka.i=m+1;
            belka.j = M;


        }
        if (belka.i!=0)
        {
            konce[belka.i]=belka.j;
            wymiar++;
            koszt+=belka.koszt;
        }

    }


    cout<<koszt<<endl;


    return 0;
}