atcoder

# # Explanation

The range of the length of C is determined once the lengths of A and B are fixed.
Sort the edges according to their length.
Find the number of the edges which are included in the range by using binary search.

# # Time complexity

$O(N^2)$ to fix A and B and $O(logN)$ to determind C with binary search.

$O(N^2logN)$

# # Solution

#define MAX_N 2001

Int N;
vector<Int> L(MAX_N, -1);

void input() {
cin >> N;
loop(i,0,N) cin >> L[i];
}

void solve() {
sort(span(L,0,N));  // sort edges by length asc

Int count = 0;
//O(N^2)
loop(a,0,N-2) {
loop(b,a+1,N) {
Int min_c = L[a] - L[b] + 1;
Int max_c = L[a] + L[b] - 1;
// Binary search twice. O(2LogN)
count += upper_bound(span(L,b+1,N), max_c) - lower_bound(span(L,b+1,N), min_c);
}
}
cout << count << endl;
}

int main() {
input();
solve();
return 0;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!