Cod sursa(job #927807)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 26 martie 2013 01:22:28
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#define Nmax 30000

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

long long N, R;
int V[Nmax], hash[Nmax * 2];

void citire(){

    ifstream f(FileIn);

    f >> N;

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

    f.close();
}


void rezolva(){

    int j = 0;

    for ( int i = 1; i <= V[N - 1] + V[N]; ++i ){

        while ( j <= N && V[j] <= i)
            ++j;

       j--;

        hash[i] = j;
    }


    for ( int i = 1; i < N; ++i )
        for ( int j = i + 1; j <= N; ++j )
            if ( hash[ V[i] + V[j] ] > j )
                R += hash[ V[i] + V[j] ] - j;
}

void afis(){

    ofstream g(FileOut);

    g << R << "\n";

    g.close();
}


int main(){

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

    return 0;
}