Cod sursa(job #1701149)
| Utilizator | Data | 12 mai 2016 11:23:21 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.62 kb |
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int v[800+5],n;
void cautare(int i,int j,int&poz){
int prod=1<<10;
while(prod>=1){
if(poz+prod<n && v[poz+prod]<=v[i]+v[j])
poz+=prod;
prod/=2;
}
}
int main()
{
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
int poz,nrtri=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
cin>>v[i];
sort(v+0,v+n);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
poz=j;
cautare(i,j,poz);
nrtri+=poz-j;
}
}
cout<<nrtri;
return 0;
}
