Cod sursa(job #3253844)

Utilizator Radu_GrigorieGrigorie Radu Stefan Radu_Grigorie Data 4 noiembrie 2024 23:29:40
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 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++)
    {
        for(int j=i+1; j<=n; j++)
        {
            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;
}