Cod sursa(job #1594360)

Utilizator valentin50517Vozian Valentin valentin50517 Data 9 februarie 2016 14:21:47
Problema Numarare triunghiuri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <algorithm>
 
using namespace std;
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");
 
bool comp(int a,int b) {return a < b;}
int N,A[1000],rs;

int cbin(int lim,int val){
    int step,i;
    for(step = 1;step <= lim;step<<=1);
    for(i = 1;step;step>>=1)
        if(i+step <= lim && A[i+step] <= val)
            i+=step;
    return i;
}
 
int main(){
    fin >> N;
    for(int i = 1;i<=N;i++){
        fin >> A[i];
    } 
     
    sort(A,A+N,comp);
    for(int i = 1;i<=N-2;i++)
        for(int j = i+1;j<=N-1;j++){
			int k = cbin(N,A[i]+A[j]);
			rs+=k-j-bool(A[k] > A[i]+A[j]);
        }
    fout << rs;
             
             
    return 0;
}