Cod sursa(job #2072015)

Utilizator SchnitzelMannPavaloiu Gabriel SchnitzelMann Data 21 noiembrie 2017 12:10:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 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=2;i<n;i++)
        for(j=1;j<i;j++)
        {
            r=0;
            pas=1<<10;
            while(pas)
            {
                if(r+pas<=n&&arr[r+pas]<=arr[i]+arr[j])
                    r+=pas;
                pas>>=1;
            }
            if(r>i)
                s+=r-i;
        }
    out<<s;
    return 0;
}