Cod sursa(job #2453887)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 6 septembrie 2019 13:34:23
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

#include <fstream>
ifstream cin("nrtri.in"); ofstream cout("nrtri.out");

int v[805];
int n;

int main() {

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}

	sort(v + 1, v + n + 1);

	int ans = 0;

	for (int i = 1; i <= n - 2; i++) {
		for (int j = i + 1; j <= n - 1; j++) {
			int st = j;
			int dr = n;
			int stop = 0;
			while (st <= dr) {
				int mid = st + dr;
				mid /= 2;
				if (v[mid] <= v[i] + v[j]) {
					stop = mid;
					st = mid + 1;
				}
				else {
					dr = mid - 1;
				}
			}
			ans += stop - j;
		}
	}

	cout << ans;
	return 0;
}