Cod sursa(job #2094446)
| Utilizator | Data | 25 decembrie 2017 21:30:15 | |
|---|---|---|---|
| Problema | Numarare triunghiuri | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.53 kb |
#include<bits/stdc++.h>
using namespace std;
int a[1000],rs,n;
int BS(int low, int high, int v) {
while (low<=high) {
int mid=(low+high)/2;
if (a[mid]>v) high=mid-1;
else low=mid+1;
}
low--;
if (a[low]<=v) {
return low;
}
}
int main() {
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
cin>>n;
for (int i=0; i<n; i++) cin>>a[i];
sort(a,a+n);
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
rs=rs+BS(j+1, n-1, a[i]+a[j])-j;
}
}
cout<<rs;
return 0;
}
