Cod sursa(job #3175016)

Utilizator fortyforBroscoi Mihai fortyfor Data 25 noiembrie 2023 11:31:47
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>
int main()
{
    unsigned short n;
    fin >> n;
    unsigned short Stix[n];
    for (int i=0;i<n;i++)
    {
        fin >> Stix[i];
    }
    std::sort(Stix+1, Stix+n+1);
    unsigned long long s=0;
    for (unsigned int i=0;i<n-2;i++)
    {
        for (unsigned int j=i+1;j<n-1;j++)
        {
            unsigned int target=Stix[i]+Stix[j],l=j,r=n-1,probe,ans=0;
            while (l<=r) {
                probe=(l+r)/2
                if (target<=Stix[probe]) {
                    if (Stix[probe-1]>=target) {
                        r=target;
                    } else {
                        ans=probe;
                        break;
                    }
                } else {
                    if (Stix[probe+1]<=target) {
                        l=target;
                    }
                }
            }
            s+=n-ans;
        }
    }
    fout << s;
    return 0;
}