Pagini recente » Cod sursa (job #3181883) | Cod sursa (job #2032418) | Cod sursa (job #2593730) | Cod sursa (job #2101909) | Cod sursa (job #2896107)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int main(){
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n;i++){
int x;
cin >> x;
arr[i] = x;
}
sort(arr,arr+n);
int cnt = 0;
int sum = 0;
for (int i = 0; i < n-2;i++){
for (int j = i + 1; j < n-1;j++){
sum = arr[i] + arr[j];
///search with binary search for v[k]<=sum<=v[k+1] and increase cnt with n-k
int st = j + 1, dr = n - 1, k = 0;
while(st<=dr){
int mij = (st + dr) / 2;
if(arr[mij]<=sum){
st = mij + 1;
k = mij;
}
else dr = mij - 1;
}
if(k!=0)
cnt += k - j;
}
}
cout << cnt;
return 0;
}