Cod sursa(job #1835943)

Utilizator CodrinsahCotarlan Codrin Codrinsah Data 27 decembrie 2016 16:11:37
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.55 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi ("nrtri.in");
ofstream fo ("nrtri.out");
int a[1000],i,j,n,s,st,dr,mij,sol,poz;
int main()
{
    fi>>n;
    for (i=1;i<=n;i++) fi>>a[i];
    sort (a+1,a+n+1);
    for (i=1;i<n-1;i++)
      for (j=i+1;j<n;j++)
    {
      s=a[i]+a[j];
      st=j+1;
      dr=n;
      poz=0;
      while (dr>=st)
      {
        mij=(dr+st)/2;
        if (a[mij]<=s) {st=mij+1;poz=mij;}
        else dr=mij-1;
      }
      if (poz!=0) sol+=poz-j;
    }
    fo<<sol;
    return 0;
}