Cod sursa(job #3130015)

Utilizator VladdStoicaStoica Vlad VladdStoica Data 16 mai 2023 17:26:09
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
int n, v[801], poz, cnt=0;
int main()
{
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i];
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        if(v[i]>v[j])
            swap(v[i],v[j]);
    }
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
        int s=v[i]+v[j];
        int dr=n, st=1, mij;
        poz=-1;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij]>s)
                dr=mij-1;
            else
            {
                st=mij+1;
                poz=mij;
            }
        }
        if(poz!=-1)
            cnt+=poz-j;
    }
    cout<<cnt;
    return 0;
}