Cod sursa(job #1161349)

Utilizator BologaDragosBologa Dragos BologaDragos Data 31 martie 2014 10:35:20
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <algorithm>
#define constant 512

using namespace std;

ifstream f("nrtri.in") ;
ofstream g("nrtri.out") ;

int v[801],n ;

int main()
{
    int i,ct=0,j,k,p  ;
    f>>n ;
    for(i=1;i<=n;i++)
        f>>v[i] ;
    sort(v+1,v+n+1) ;
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++)
        {
           p=constant ;
           k=j+1 ;
           while(p)
           {
               if(p+k<=n&&v[p+k]<=v[i]+v[j])
                    k+=p ;
               p/=2 ;
           }
           if(v[k]<=v[i]+v[j])
                ct+=k-j ;
        }

    g<<ct ;
    return 0;
}