Cod sursa(job #1205952)
Utilizator | Pavlov Ion pavlov.ion | Data | 8 iulie 2014 15:27:22 |
---|---|---|---|
Problema | Numarare triunghiuri | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.65 kb |
#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int N,V[805],s;
int bsearch(int st,int dr,int val)
{
int mid;
while(st<=dr){
mid=(st+dr)/2;
if(V[mid]<=val)
st=mid+1;
else dr=mid-1;
}
mid=(st+dr)/2;
while(V[mid]>val)
mid--;
return mid;
}
int main () {
int i,j,k;
cin>>N;
for(i=1;i<=N;i++)
cin>>V[i];
sort(V+1,V+N+1);
for(i=1;i<=N-2;i++)
for(j=i+1;j<=N-1;j++){
k=bsearch(j+1,N,V[i]+V[j]);
if(k>j-1)
s=s+(k-j);
}
cout<<s;
return 0;
}