Cod sursa(job #927797)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 martie 2013 00:59:10
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#define Nmax 40002

char FileIn [] = { "nrtri.in" };
char FileOut [] = { "nrtri.out" };

int N, R;
int V[Nmax], Vmin[Nmax];

void citire(){

    ifstream f(FileIn);

    f >> N;

    for ( int i = 1; i <= N; ++i )
        f >> V[i];

    f.close();
}


int cautare ( int st, int dr, int x ) {

    int m;

    if ( V[dr] <= x )
        return dr;
    else
        if ( x < V[1] )
            return 0;

    while ( st <= dr ) {

        m = (dr - st) / 2 + st;

        if ( V[m] <= x && x < V[m + 1] )
            return m;
        else
            if ( x < V[m])
                dr = m - 1;
            else
                st = m + 1;
    }

    return 0;
}

void rezolva(){

    for ( int i = 0; i <= Nmax + Nmax; i++ )
        Vmin[i] = cautare ( 1, N, i );

    for ( int i = 1; i < N; i++ )
        for ( int j = i + 1; j <= N; j++ ) {

            int maxim = Vmin[ V[i] + V[j] ];

            R += max ( maxim - j, 0 );
        }
}

void afis(){

    ofstream g(FileOut);

    g << R << "\n";

    g.close();
}


int main(){

    citire();
    sort ( V + 1, V + N + 1 );
    rezolva();
    afis();

    return 0;
}