Cod sursa(job #2072005)

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