Cod sursa(job #1610950)

Utilizator florinasAsavei florinas Data 23 februarie 2016 20:47:23
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>
#include<stdlib.h>

int v[30720], val[1024];

int cmp(const void *a, const void *b)
{
    return *(int *)b - *(int *)a;
}


int main()
{
    freopen("nrtri.in", "r", stdin);
    freopen("nrtri.out", "w", stdout);

    int n, i, j, k, sol=0;

    scanf("%d", &n);

    for (i=1; i<=n; i++)
    {
        scanf("%d", &val[i]);
        ++v[val[i]];
    }


    for (i=1; i<=30000; i++)
        v[i]+=v[i-1];

    qsort(val+1, n, sizeof(int), cmp);

    if (n<100)
    {
        for (i=1; i<n-1; i++)
            for (j=i+1; j<n; j++)
                for (k=j+1; k<=n; k++)
                    if (((val[i]<=val[j]+val[k]) && (val[i]>=val[j]) && (val[i]>=val[k])) || ((val[j]<=val[i]+val[k]) && (val[j]>=val[i]) && (val[j]>=val[k])) || ((val[k]<=val[i]+val[j]) && (val[k]>=val[i]) && (val[k]>=val[j])))  sol++;
        printf("%d", sol);
        return 0;
    }

    for (i=1; i<n-1; i++)
        for (j=i+1; j<n; j++)
            if (val[i]-val[j] <= val[j]) sol+=v[val[j]] - v[val[i]-val[j]-1]-1 -(val[j]==val[j-1]);

    printf("%d", sol);
    return 0;
}