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 #include #include #include #include using namespace std; #define ll long long #define ld long double #define vi vector #define pb push_back #define pii pair #define mp make_pair #define st first #define nd second #define mini(a,b) a=min(a,(b)) #define maxi(a,b) a=max(a,(b)) #define RE(i,n) for(int i=0,_n=(n);i<_n;++i) #define RI(i,n) for(int i=1,_n=(n);i<=_n;++i) const int inf=1e9+5, nax=2e3+5; vector > wp; int n; bool t[nax][nax]; vector kol; int start[nax], koniec[nax]; void dodaj(int a, int b) { if(a < 1 || b > n || t[a][b]) return; kol.pb(mp(a, b)); t[a][b] = true; } void dodaj_main(int a, int b) { if(b + 1 <= start[a]) dodaj(b + 1, start[a]); else dodaj(start[a] + 1, b); if(a <= koniec[b] - 1) dodaj(a, koniec[b] - 1); else dodaj(koniec[b], a - 1); dodaj(a, start[b + 1]); dodaj(koniec[a - 1], b); } int main() { scanf("%d", &n); RE(i, n + 3) start[i] = inf; RI(i, n) for(int j = i; j <= n; ++j) { int a; scanf("%d", &a); wp.pb(mp(a, mp(i, j))); } RI(i, n) RI(j, n) t[i][j] = false; sort(wp.begin(), wp.end()); ll RES = 0; RE(i, wp.size()) if(!t[wp[i].nd.st][wp[i].nd.nd]) { RES += (ll) wp[i].st; dodaj(wp[i].nd.st, wp[i].nd.nd); for(int j = 0; j < (int) kol.size(); ++j) dodaj_main(kol[j].first, kol[j].second); RE(j, kol.size()) { mini(start[kol[j].st], kol[j].nd); maxi(koniec[kol[j].nd], kol[j].st); } kol.clear(); } printf("%lld", RES); return 0; }