Cod sursa(job #3253839)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 4 noiembrie 2024 23:04:59
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int v[3005];
int main()
{
    int n, cnt=0;
    fin >> n;
    for(int i=1; i<=n; i++)
    {
        fin >> v[i];
    }
    sort(v+1, v+n+1);
    for(int i=1; i<=n; i++)
    {
        if(v[i]!=v[i-1])
        {
            for(int j=i+1; j<=n; j++)
            {
                if(v[i]+v[j]<=v[n]&&(v[j]!=v[j-1]||j==i+1))
                {
                    int st=0, dr=n+1, mid;
                    while(st<dr-1)
                    {
                        mid=(st+dr)/2;
                        if(v[mid]>v[i]+v[j])
                            dr = mid;
                        else
                            st = mid;
                    }
                    cnt+=(st-j);
                }
            }
        }
    }
    fout << cnt;
    return 0;
}