Cod sursa(job #3296640)

Utilizator filipdanieloanFilip-Daniel Oancea filipdanieloan Data 14 mai 2025 22:44:10
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("nrtri.in");
ofstream cout("nrtri.out");

int n;
int v[801], cnt = 0;

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

	for(int i = 1; i <= n; i ++) {
		int a = v[i];
		for(int j = i+1; j <= n; j ++) {
			int b = v[j];
			int st = j+1, dr = n, cautare = -1;
			while(st <= dr) {
				int mij = (st+dr)/2;
				if(v[mij] <= a+b) {
					cautare = mij;
					st = mij + 1;
				} else
					dr = mij - 1;
			}
			if(cautare != -1)
				cnt += (cautare - j);
		}
	}

	cout << cnt;
}