Cod sursa(job #2276223)

Utilizator GabiGabrielAndrei Gabriel GabiGabriel Data 4 noiembrie 2018 13:39:37
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<fstream>
using namespace std;
int v[801], i, j, n, st, dr, I, x, mid;
int main() {
	ifstream fin("nrtri.in");
	ofstream fout("nrtri.out");
	fin >> n;
	int sol = 0;
	for (i = 1; i <= n; i++)
		fin >> v[i];
	for (i = 1; i <= n - 1; i++)
		for (j = i + 1; j <= n; j++)
			if (v[i] > v[j]) {
				I = v[i];
				v[i] = v[j];
				v[j] = I;
			}
	for (i = 1; i < n - 1; i++)
		for (j = i + 1; j <= n - 1; j++) {
			st = j + 1;
			dr = n;
			x = v[i] + v[j];
			while (st <= dr) {
				mid = (st + dr) / 2;
				if (x<v[mid])
					dr = mid - 1;
				else
					st = mid + 1;
			}
			sol += dr - j;
		}
	fout << sol;
	return 0;
}