Cod sursa(job #3196339)

Utilizator Vladimir_AlbuVladimir Albu Vladimir_Albu Data 23 ianuarie 2024 18:25:46
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#pragma GCC optimize("Ofast,unroll-loops")

#include <fstream>
#include <algorithm>

using namespace std;

#define FILE_NAME "nrtri"

ifstream fin(FILE_NAME ".in");

#ifdef LOCAL
	#include <iostream>
	#define fout cout
#else
	ofstream fout(FILE_NAME ".out");
#endif

#define lsb(x) (x & (-x))
#define popcount(x) __builtin_popcount(x)

#define fi first
#define se second

#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

using ll = long long;
using ld = long double;

using pii = pair<int, int>;

const int NMAX = 2e3 + 5;
const int INF = 1e9 + 5;

int N;

int a[NMAX];

void read() {
	fin >> N;

	for(int i = 1; i <= N; i++) {
		fin >> a[i];
	}

	fin.close();
}

int res = 0;

void solve() {
	int x, y;

	int low, high;

	int mid;

	sort(a + 1, a + N + 1);

	for(int i = 1; i < N - 1; i++) {
		for(int j = i + 1; j < N; j++) {
			x = a[i];
			y = a[j];

			low = j + 1;
			high = N;

			while(low <= high) {
				mid = (low + high) / 2;

				if(a[mid] <= x + y) {
					low = mid + 1;		
				} else {
					high = mid - 1;
				}
			}

			res += high - j;
		}
	}

	fout << res << '\n';

	#ifndef LOCAL
		fout.close();
	#endif
}

signed main() {

	read();

	solve();

	return 0;
}