Cod sursa(job #1401831)

Utilizator ThomasFMI Suditu Thomas Thomas Data 26 martie 2015 10:09:07
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define NMax 805

ifstream f("nrtri.in");
ofstream g("nrtri.out");

int n;
int v[NMax];

int bs(int x)
{
    int j,step;
    for(step=1;step<=n;step<<=1);
    for(j=0;step;step>>=1) if(j+step<=n && v[j+step]<=x) j+=step;
    return j;
}

int sol;

int main()
{
    int i,j;

    f>>n;
    for(i=1;i<=n;++i) f>>v[i];
    sort(v+1,v+n+1);

    for(i=1;i<n;++i) for(j=i+1;j<=n;++j) sol += bs(v[i]+v[j])-j;

    g<<sol<<"\n";

    f.close();
    g.close();
    return 0;
}