Cod sursa(job #1741573)

Utilizator Bulgaru_Robert_Razvan_323CBBulgaru Robert Razvan Bulgaru_Robert_Razvan_323CB Data 14 august 2016 13:47:16
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
ifstream in("nrtri.in");
ofstream out("nrtri.out");
 
int n,v[801];

int search(int low,int val) {
    int last=-1,mid,l=low+1,h=n;

    while (l<=h) {
        mid=l+(h-l)/2;

        if (v[mid]<=val) {
            last=mid;
            l=mid+1;
        }
        else {
            h=mid-1;
        }
    }

    if (last!=-1)
        return last-low;
    
    return 0;
}
 
int main() {
    int nr=0;

    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i];
 
    sort(v+1,v+n+1);
 
    for(int i=1; i<=n-2; i++) {
        for(int j=i+1; j<=n-1; j++) {
            nr=nr+search(j,v[i]+v[j]);
        }
    }
 
    out<<nr;
    return 0;
}