Cod sursa(job #2104136)

Utilizator brczBereczki Norbert Cristian brcz Data 11 ianuarie 2018 11:01:09
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define int long long

const int maxn = 100003;
const int maxk = 1003;

int n;
vector<int> v;

int32_t main(){

	freopen("nrtri.in","r",stdin);
	freopen("nrtri.out","w",stdout);

	ios_base::sync_with_stdio(false);
	cin.tie(0);

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

	sort(v.begin(),v.end());
	int ans = 0;
	for(int i=0;i<n-1;++i) {
		for(int j=i+1;j<n;++j) {
			int lb = max(v[i]-v[j],v[j]-v[i]);
			int ub = v[i] + v[j];
			vector<int>::iterator low,upp;
			low = lower_bound(v.begin(),v.end(),lb);
			upp = upper_bound(v.begin(),v.end(),ub+1);
			int res = upp - low;
			if(lb <= v[i] && v[i] < ub+1) res--;
			if(lb <= v[j] && v[j] < ub+1) res--;
			ans += res;
		}
	}
	cout << ans / 3 << '\n';


	return 0;
}