Cod sursa(job #2155487)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 7 martie 2018 21:10:42
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<cstdio>
#include<algorithm>
using namespace std;
long long f2[60005],v[805],f[60005];
int main(){
freopen("nrtri.in","r",stdin);
freopen("nrtri.out","w",stdout);
long long n,i,j,u;
long long rasp=0;
scanf("%lld",&n);
for(i=1;i<=n;i++)
scanf("%lld",&v[i]),f[v[i]]++;
for(i=1;i<=60000;i++)
f2[i]=f2[i-1]+f[i];
sort(v+1,v+n+1);
u=1;
for(i=2;i<=n;i++)
if (v[i]!=v[i-1])
v[++u]=v[i];
n=u;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
if (v[i]!=v[j]){
rasp=rasp+(f2[v[i]+v[j]]-f2[v[j]])*f[v[i]]*f[v[j]];
rasp=rasp+f[v[i]]*f[v[j]]*(f[v[j]]-1)/2;}
else
if (f[v[i]]>=2){
rasp=rasp+(f2[v[i]+v[j]]-f2[v[j]])*f[v[i]]*(f[v[i]]-1)/2;
rasp=rasp+f[v[i]]*(f[v[i]]-1)*(f[v[i]]-2)/6;}
printf("%lld\n",rasp);
return 0;}