Cod sursa(job #1641395)

Utilizator silkMarin Dragos silk Data 8 martie 2016 22:48:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int v[805];

int main(){
    freopen("nrtri.in","r",stdin);
    freopen("nrtri.out","w",stdout);

int n,i,j,st,dr,mid,ok,maxim,total = 0;
    scanf("%d",&n);

for(i=1;i<=n;++i) scanf("%d",&v[i]);

sort(v+1,v+n+1);

for(i=1;i<=n-2;++i)
    for(j=i+1;j<=n-1;++j)
    {
        maxim = v[i] + v[j];
        for(ok=0,st=j,dr=n;st<=dr; )
        {
                mid = (st+dr)/2;
                if( v[mid] <= maxim ) { st = mid + 1; ok = mid; }
                else dr = mid - 1;
        }

if(ok) total += ok - j;
    }

printf("%d\n",total);


return 0;
}