Cod sursa(job #2487488)

Utilizator AltexStefanButacu Stefan AltexStefan Data 4 noiembrie 2019 20:46:41
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int main()
{
    int a[2005],n,i,j,k,nr=0;
    int s,st,dr,m;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
        {
            s=a[i]+a[j];
            st=j+1;
            dr=n;
            while(st<=dr)
            {
                m=(st+dr)/2;
                if(a[m]<s)
                    {
                    	nr=nr+m-st+1;
                        st=m+1;

                    }
                else dr=m-1;
            }
        }
    }
    cout<<nr;
    return 0;
}