Cod sursa(job #1842536)

Utilizator Walrus21andrei Walrus21 Data 7 ianuarie 2017 04:11:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <stdio.h>
#include <algorithm>
#define N 801

using namespace std;

int i, j, n, nr, v[N];

int cb(int x, int l, int r)
{
    int mid, p = j;
    while(l <= r)
    {
        mid = l + (r - l) / 2;
        if(v[mid] <= x) {l = mid + 1; p = mid;}
        else r = mid - 1;
    }
    return p;
}

int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &v[i]);
    stable_sort(v, v + n);
    for(i = 0; i < n - 2; i++)
        for(j = i + 1; j < n - 1; j++)
            nr += cb(v[i] + v[j], j + 1, n - 1) - j;
    printf("%d", nr);
}