Pagini recente » Cod sursa (job #2908593) | Cod sursa (job #631582) | Cod sursa (job #2529758) | Cod sursa (job #2969902) | Cod sursa (job #2857522)
// Numarare triunghiuri.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#define DIM 806
std::ifstream fin("nrtri.in");
std::ofstream fout("nrtri.out");
using namespace std;
typedef long long ll;
int N, A[DIM];
ll ans = 0;
void Read()
{
fin >> N;
for (int i = 1; i <= N; i++)
fin >> A[i];
}
int BinarySearch(int st, int dr, int x)
{
int poz = -1;
while (st <= dr)
{
int mij = (st + dr) / 2;
if (A[mij] <= x)
{
poz = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
return poz;
}
void Solve()
{
for (int i = 1; i <= N; i++)
for (int j = i + 1; j <= N; j++)
{
int poz = BinarySearch(j + 1, N, A[i] + A[j]);
if (poz != -1)
ans = 1LL * (ans + poz - j);
}
fout << ans;
}
int main()
{
Read();
sort(A + 1, A + N + 1);
Solve();
return 0;
}