Cod sursa(job #2228514)

Utilizator patcasrarespatcas rares danut patcasrares Data 4 august 2018 00:12:55
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include<fstream>
#include<algorithm>
#define DN 805
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
int n,a[DN],st,dr,mij,rez,f;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    sort(a+1,a+n+1);
    for(int i=n;i>2;i--)
        for(int j=i-1;j>1;j--)
        {
            st=1;
            dr=j-1;
            f=a[i]-a[j];
            if(a[i]>a[j]+a[j-1])
                continue;
            while(st<dr)
            {
                mij=(st+dr)/2;
                if(a[mij]>=f)
                    dr=mij;
                else
                    st=mij+1;
            }
            rez+=j-st;
        }
    fout<<rez;
}