Cod sursa(job #1956496)

Utilizator GeorginskyGeorge Georginsky Data 6 aprilie 2017 19:52:48
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define N 805
using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
unsigned long long s;
int n, v[N];

int bS(int x, int l, int r){
    int m, L=l, R=r;
    l--, r++;
    while(r-l>1){
        m=(l+r)>>1;
        if(v[m]<=x)l=m;
        else r=m;
    }
    if(v[l]<=x&&L<=l&&l<=R)return l;
    else return -1;
}

int main(){
    in>>n;
    for(int i=1; i<=n; i++)in>>v[i];
    sort(v+1, v+n+1);
    int pos;
    for(int i=1; i<n-1; i++){
        for(int j=i+1; j<n; j++){
            pos=bS(v[i]+v[j], j+1, n);
            if(pos!=-1)s+=pos-j;
        }
    }
    out<<s;
    return 0;
}