Cod sursa(job #3175016)
Utilizator | 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;
}