Cod sursa(job #2094446)

Utilizator DimaTCDima Trubca DimaTC 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;
}