Cod sursa(job #2072008)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 21 noiembrie 2017 12:04:13
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int arr[801];
int main()
{
    int n,i,j,l,r,pas,s=0;
    in>>n;
    for(i=1;i<=n;i++)
        in>>arr[i];
    sort(arr,arr+n+1);
    for(i=3;i<=n;i++)
        for(j=2;j<i;j++)
        {
            r=0;
            pas=1<<10;
            while(pas)
            {
                if(r+pas<j&&arr[i]<=arr[j]+arr[r+pas])
                    r+=pas;
                pas>>=1;
            }
            l=0;
            pas=1<<10;
            while(pas)
            {
                if(l+pas<j&&arr[i]>arr[j]+arr[l+pas])
                    l+=pas;
                pas>>=1;
            }
            if(r>l)
                s+=r-l;
        }
    out<<s;
    return 0;
}