Cod sursa(job #3152359)

Utilizator sorinturdaSorin Turda sorinturda Data 24 septembrie 2023 19:02:43
Problema Numarare triunghiuri Scor 0
Compilator c-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
//https://www.infoarena.ro/problema/nrtri
#include <stdio.h>
#include <stdlib.h>
const int N = 800;
int comparator(const void *a, const void *b){
	return (*(int*)a - *(int*)b);
}

int main(){
	int a[N],n, ans=0;
	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d", a+i);
	qsort(a,n,sizeof(int),comparator);
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n-1;j++){
			int x=a[i]+a[j],st=j+1,dr=n-1,mid;
			if(x > a[n-1])
				continue;
			while(st<=dr){
				mid = st + (dr-st)/2;
				if(a[mid] <= x)
					st = mid + 1;
				else
					dr = mid - 1;
			}
			ans+=(n-dr-1);
		}
	printf("%d\n",ans);
	return 0; 
}