Cod sursa(job #654115)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 29 decembrie 2011 16:30:39
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <algorithm>
int i,j,n,a[805],s;
using namespace std;
ifstream f("nrtri.in");
ofstream g("nrtri.out");
int bs(int x )
{
        int st=1,dr=n,m=0;
        while (st<=dr) {
                m=(st+dr)/2;
                if (x<=m) dr=m;
                else st=m+1;
        }
        if (a[m]>x)  return m-1; else return m;
}
int main()
{
        f>>n;
        for(i=1; i<=n; i++) f>>a[i];
        sort(a+1,a+n+1);

        for(i=1; i<=n-2; i++)
                for(j=i+1; j<=n-1; j++)
                s+=max(0,bs(a[i]+a[j])-j);
g<<s;
        f.close();
        g.close();
        return 0;
}