Cod sursa(job #1451970)

Utilizator theprdvtheprdv theprdv Data 19 iunie 2015 12:28:44
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#define _CRT_SECURE_NO_DEPRECATE
#include <algorithm>

int N, X[801], sol, LOG;

int search(int val){
	int step = LOG, k = 0;

	for (; step; step >>= 1)
		if (k + step > N) continue;
		else if (X[k + step] <= val) k += step;
	return k;
}

int main(void)
{
	freopen("nrtri.in", "r", stdin);
	freopen("nrtri.out", "w", stdout);

	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &X[i]);
	std::sort(X + 1, X + N + 1);
	for (LOG = 1; LOG <= N; LOG <<= 1);

	for (int i = 1; i < N - 1; ++i)
		for (int j = i + 1; j < N; ++j){
			int pos = search(X[i] + X[j]);
			if (pos <= j) continue;
			if (pos) sol += pos - j;
		}
	printf("%d", sol);

	return 0;
}