#include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long LL; #define REP(i,n) for(int i=0;i<(n);++i) #define PB push_back #define ALL(V) (V).begin(),(V).end() const int MAX = 2010; struct query { int b, e, c; bool operator<(const query &rhs) const { return c < rhs.c; } }; vector<query> Q; int E[MAX], len[MAX], cc[MAX]; int n; int main(int argc, char *argv[]) { scanf("%d", &n); Q.reserve(n*n); REP(i,n) { for(int j=i;j<n;j++) { int c; scanf("%d", &c); Q.PB({i, j, c}); } len[i] = E[i] = -1; cc[i] = i; } sort(ALL(Q)); LL res = 0; for(auto q : Q) { int b = q.b, e = q.e; if(E[e] != -1 && cc[b] == cc[E[e]]) continue; res += q.c; while(len[b] != -1) { if(len[b] < e-b+1) b += len[b]; else { int l = len[b] - (e-b+1); b = e+1; e = b+l-1; } } while(b != -1) { while(E[e] != -1 && len[E[e]] < e-b+1) e = E[e]-1; len[b] = e-b+1; int nextb = -1, nexte = -1; if(E[e] != -1) nextb = E[e], nexte = b-1; E[e] = b; b = nextb, e = nexte; } REP(i,n) cc[i] = -1; REP(i,n) if(cc[i] == -1) { cc[i] = i; for(int t=i;t<n && len[t] != -1;t+=len[t]) cc[t] = i; } } printf("%lld\n", res); return 0; }
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 | #include <algorithm> #include <cstdio> #include <vector> using namespace std; typedef long long LL; #define REP(i,n) for(int i=0;i<(n);++i) #define PB push_back #define ALL(V) (V).begin(),(V).end() const int MAX = 2010; struct query { int b, e, c; bool operator<(const query &rhs) const { return c < rhs.c; } }; vector<query> Q; int E[MAX], len[MAX], cc[MAX]; int n; int main(int argc, char *argv[]) { scanf("%d", &n); Q.reserve(n*n); REP(i,n) { for(int j=i;j<n;j++) { int c; scanf("%d", &c); Q.PB({i, j, c}); } len[i] = E[i] = -1; cc[i] = i; } sort(ALL(Q)); LL res = 0; for(auto q : Q) { int b = q.b, e = q.e; if(E[e] != -1 && cc[b] == cc[E[e]]) continue; res += q.c; while(len[b] != -1) { if(len[b] < e-b+1) b += len[b]; else { int l = len[b] - (e-b+1); b = e+1; e = b+l-1; } } while(b != -1) { while(E[e] != -1 && len[E[e]] < e-b+1) e = E[e]-1; len[b] = e-b+1; int nextb = -1, nexte = -1; if(E[e] != -1) nextb = E[e], nexte = b-1; E[e] = b; b = nextb, e = nexte; } REP(i,n) cc[i] = -1; REP(i,n) if(cc[i] == -1) { cc[i] = i; for(int t=i;t<n && len[t] != -1;t+=len[t]) cc[t] = i; } } printf("%lld\n", res); return 0; } |