Cod sursa(job #2776451)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 19 septembrie 2021 20:41:14
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
/* [A][M][C][B][N] / [K][R][I][P][6][8] */
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
// Global variables
typedef long long ll;
const char sp = ' ', nl = '\n';
const int MOD = 1234567; // 666013 998244353 1000000007
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n, v[800];
int main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0); cout.tie(0);
	fin >> n;
	for (int i = 0; i < n; i++) fin >> v[i];
	sort(v, v + n);
	int cnt(0);
	for (int i = 0; i < n - 2; i++)
		for (int j = 1; j < n - 1; j++)
			for (int k = 2; k < n; k++) {
				if (v[i] + v[j] < v[k]) {
					cnt += k - j - 1;
					/*
					0 1 2 3
					2 3 4 7
					i = 1, j = 2
					k = 2 merge
					k = 3 e prea mare => adunam la cnt cate numere sunt intre j si k
					*/
					break;
				}
			}
	fout << cnt;
}