Cod sursa(job #1714628)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 8 iunie 2016 22:04:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <algorithm>
#define MAX 6000000
#define INF 200000005
using namespace std;
  
char f[MAX];
int pos=0,N,v[1000];
long long S=0;
void r(int &nr)
{
    nr=0;
    while(f[pos]<'0'||f[pos]>'9')
        pos++;
    while(f[pos]>='0'&&f[pos]<='9')
        nr=nr*10+f[pos++]-'0';
}
void bsearch(int check,int start)
{
	int lw=start,hi=N,mi=start;
	while(lw<=hi)
	{
		mi=(lw+hi)>>1;
		if(v[mi]>check)
			hi=mi-1;
		else if(v[mi]<check||(v[mi]==check&&v[mi+1]==check))
			lw=mi+1,hi=min(max(hi,mi+2),N);
		else
		{
			mi++;
			break;
		}
	}
	S+=mi-start;
}
int main()
{
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);
  
    fread(f,1,MAX,stdin);
	
	r(N);
	for(int i=1;i<=N;i++)
		r(v[i]);
	sort(v+1,v+N+1);
	for(int i=1;i<N-1;i++)
		for(int j=i+1;j<N;j++)
			if(v[i]+v[j]>=v[N])
				S+=N-j;
			else
				bsearch(v[i]+v[j],j+1);
	printf("%lld",S);
    return 0;
}