Cod sursa(job #2468497)

Utilizator doruliqueDoru MODRISAN dorulique Data 5 octombrie 2019 16:22:02
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
int nr[30001],a[801];

int main()
{
    int sol=0,n,i,x,m=0,j,st,dr,val;
    FILE *f=fopen("nrtri.in","r");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d",&x);
        nr[x]++;
    }
    for(i=1;i<=30000;i++)
        for(j=1;j<=nr[i];j++)
            a[++m]=i;
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++)
        {///caut binar ultima aparitzie a lui a[i]+a[j] - latura maxima pe care o putem avea
            ///daca a[i] shi a[j] sunt celelalte doua laturi
            st=j+1;dr=n;val=a[i]+a[j];
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(val>=a[m])st=m+1;
                else dr=m-1;
            }
            //dr=indicele ultimei aparitzii ale lui val
            sol+=dr-j;
        }
    f=fopen("nrtri.out","w");
    fprintf(f,"%d",sol);
    return 0;
}