Cod sursa(job #1768762)

Utilizator bogdi1bogdan bancuta bogdi1 Data 1 octombrie 2016 13:52:54
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[805];
int main()
{   freopen("nrtri.in", "r",stdin);
    freopen("nrtri.out", "w",stdout);
    int n,i,i1,i2,ii,pas,nr=0;
    scanf("%d", &n);
    for(i=1; i<=n; i++)
        scanf("%d", &v[i]);
    sort(v+1, v+n+1);
    for(i1=1; i1<=n-2; i1++)
        for(i2=i1+1; i2<=n-1; i2++){
            i=i2;
            pas=1<<10;
            while(pas!=0){
                if(i+pas<=n && v[i+pas]<abs(v[i1]-v[i2]))
                    i+=pas;
                pas/=2;
            }
            ii=i+1;
            i=ii-1;
            pas=1<<10;
            while(pas!=0){
                if(i+pas<=n && v[i+pas]<=v[i1]+v[i2])
                    i+=pas;
                pas/=2;
            }
            nr+=i-ii+1;
        }
    printf("%d", nr);
    return 0;
}