Pagini recente » Cod sursa (job #1299455) | Cod sursa (job #2334620) | Cod sursa (job #2895921) | Cod sursa (job #1328191) | Cod sursa (job #1897329)
#include<fstream>
using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int n, a[804];
int partition(int a[100], int b, int e){
int x = a[e];
int i = b-1;
for(int j=b; j<e; ++j){
if(a[j]<=x){
i++; int w;
w = a[i]; a[i] = a[j]; a[j] = w;
}
}
int sc; sc = a[i+1]; a[i+1]=a[e]; a[e] = sc;
return i+1;
}
void quicksort(int v[804], int b, int e){ if(b<e){
int p = partition(v, b, e);
quicksort(v,b, p-1); quicksort(v,p+1,e);
}}
int bsearch(int v[804], int b0, int e0){
int b = b0, e = e0;
while(b<e){
int mid; mid = (b+e)/2;
if(v[b0]+v[mid]>=v[e0]) e = mid;
else b = mid+1;
}
if(b==e0) return 0;
if(b==b0) return e0 - b - 1;
return e0-b;
}
long long nrtriunghiuri(int v[804],int m){
long long total = 0;
int x=1, z=3;
for(z=3; z<=m; ++z){
for(x=1; x<=z-2; ++x){
total=total+bsearch(v,x,z);
}
}
return total;
}
int main(){
cin>>n;
for(int i=1; i<=n; ++i) cin>>a[i];
quicksort(a, 1, n);
cout<<nrtriunghiuri(a,n);
return 0;
}