Cod sursa(job #1703732)

Utilizator pincucatalinPincu Catalin pincucatalin Data 17 mai 2016 16:01:30
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *in=fopen ("nrtri.in","r");
FILE *out=fopen ("nrtri.out","w");
int n, v[800],nr;
int main()
{
    fscanf (in,"%d",&n);
    for (int i=1;i<=n;i++)
        fscanf (in,"%d",&v[i]);
    sort (v+1,v+1+n);
    for (int i=1;i<n-1;i++)
        for (int j=i+1;j<n;j++)
        {
            int k=j,pas=1<<10;
            while (pas!=0)
            {
                if (k+pas<=n && v[k+pas]<=v[i]+v[j])
                    k+=pas;
                pas/=2;
            }
            if (k>j)
            nr+=(k-j);
        }
    fprintf (out,"%d",nr);
    return 0;
}