Cod sursa(job #943020)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 24 aprilie 2013 02:44:18
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "nrtri";

const string infile = file + ".in";
const string outfile = file + ".out";


int N;
vector<int> A;
int sol;
void citire()
{
	ifstream fin(infile.c_str());
	fin >> N;
	A.resize(N);
	for(int i = 0; i < N; i++)
	{
		fin >> A[i];
	}
	fin.close();
}

void solve()
{


	sort(A.begin(), A.end());

	for(int i = 0; i < N-2; i++)
	{
		for (int j = i+2; j < N; ++j)
		{
			int l = A[j] - A[i];

			int index = lower_bound(A.begin()+i+1, A.begin()+j, l) - A.begin();
			sol += j - index;

		}
	}

}

void afisare()
{
	ofstream fout(outfile.c_str());
	fout << sol;
	fout.close();
}

int main()
{
	citire();
	solve();
	afisare();
}