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

using namespace std;

struct Interval {
       int start;
       int size;
       unsigned long long price;
};

bool operator< (Interval a, Interval b) {
     return a.price < b.price;
}

bool insert(vector<int> &matrix, int start, int size) {
	while(true) {
		if(size == 0) {
			return false;
		} else if(matrix[start] == 0) {
			matrix[start] = size;
			return true;
		} else {
			int prevStart = start;
			start = start + min(size, matrix[start]);
			size = abs(size - matrix[prevStart]);
		}
	}
}

int main() {
    ios::sync_with_stdio(0);

    int N;
    
    cin >> N;
    
    vector<Interval> offers;
    
    for(int i = 0; i < N; i++) {
            for(int j = i; j < N; j++) {
                    Interval interval;
                    interval.start = i;
                    interval.size = j-i+1;
                    cin >> interval.price;
                    offers.push_back(interval);
            }
    }
    
    sort(offers.begin(), offers.end());
    
    vector<int> matrix(N);
    int matrixRank = 0;
    unsigned long long totalCost = 0;
    
    for(int i = 0; 2*i < N*(N+1); i++) {
            if(matrixRank == N) break;
            if(insert(matrix, offers[i].start, offers[i].size)) {
                              matrixRank++;
                              totalCost += offers[i].price;
            }
    }
    
    cout << totalCost << endl;
    
	return 0;
}