Cod sursa(job #2164286)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 12 martie 2018 22:37:26
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

ifstream f("nrtri.in");
ofstream g("nrtri.out");
int n, sol, v[805];
void read()
{
    f >> n ;
     for ( int i = 1 ;i <= n ;i ++ )
       f >> v[i];
    sort(v+1,v+n+1);
}
int bsearch(int val,int s)
{
    int dr=n,st=s;
    int mj=0;
      while(st <= dr)
       {
           mj=(st+dr)/2;
            if (v[mj]>val)
             {
                dr=mj-1;
             }
             else
             st=mj+1;
       }
    return dr-s;
}
void solve()
{
    for ( int i = 1 ; i <= n -2 ; i ++ )
      for ( int j = i + 1 ; j <= n-1 ; j ++ )
        {
            sol+=bsearch(v[i]+v[j],j);
        }
    g << sol;
}
int main()
{
    read();
    solve();
    return 0;
}