Cod sursa(job #1287801)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 8 decembrie 2014 00:28:43
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n,i,j,u,p;
int us[30006],v[850],sum[30006],sol;
int main()
{
    freopen( "nrtri.in" , "r" , stdin );
    freopen( "nrtri.out", "w" , stdout);
    scanf("%d\n" , &n);
    for(i=1;i<=n;++i){ scanf("%d ", &v[i]); us[v[i]]++; }
    for(i=1;i<=30000;++i) sum[i] = sum[i-1] + us[i];
    sort( v , v + n + 1 );
    for(i=1;i< n;++i)
        for(j=i+1;j<=n;++j){
            u=v[i]+v[j];
            if(u>30000) u = n;
            else        u = sum[u];
            p = v[j]-v[i];
            p = sum[p-1]+1;
            sol += u-p+1- (i >= p && i <=u) - (j >= p && j <= u);
        }
    printf("%d\n",sol/3);
    return 0;
}