Cod sursa(job #1768258)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 30 septembrie 2016 16:37:22
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

int v[870],sum=0;

int main()
{
    ifstream fin ("nrtri.in");
    ofstream fout ("nrtri.out");
    int n;
    fin>>n;
    for (int i=0;i<n;++i)
    {
        fin>>v[i];
    }
    sort (v,v+n);
    for (int i=0;i<n-2;++i)
    {
        for (int j=i+1;j<n-1;++j)
        {
            int x=v[i]+v[j];
            //cout<<"x="<<x<<"     ";
            int s=j+1,d=n-1,sol=0;
            while (s<=d)
            {
                int mij=(d+s)/2;
                 if (x>=v[mij])
                {
                    sol=mij;
                    s=mij+1;
                }
                else
                {
                    d=mij-1;
                }
            }
            //cout<<v[mij]<<"    "<<v[i]<<"  "<<v[j]<<endl;
            if (sol!=0)
            {
            sum=sum+sol-j;
            }
        }
    }
    fout<<sum;
}