Cod sursa(job #1698642)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 4 mai 2016 22:18:00
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#define NMAX 805
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int v[NMAX];

int main() {
	int i,n,t,st,dr,mid,s,last,res=0,j;

	fin>>n;

	for(i=1;i<=n;++i) fin>>v[i];

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

	for(i=1;i<=n;++i) {
		for(j=i+1;j<=n;++j) {
			last=0;
			st=j+1;
			dr=n;
			s=v[i]+v[j];
			while(st<=dr) {
				mid=((st+dr)>>1);

				if(v[mid]<=s) {
					st=mid+1;
					last=mid;
				}
				else dr=mid-1;
			}

			if(last) res+=last-j;
		}
	}

	fout<<res;

	return 0;
}