Cod sursa(job #2444826)

Utilizator bl1nk3rFilip Corlan bl1nk3r Data 1 august 2019 16:07:10
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int a[801];

void cbin(int s, int d, int x,int &r) {

    long long m;

    if(s <= d) {

     m = (s + d) / 2;

     if(a[m] <= x) {

            r = m;

        cbin(m+1, d, x, r);

     } else if(a[m] > x)

        cbin(s, m-1, x, r);
    }

}

int main()
{
    ifstream cin("nrtri.in");
    ofstream cout("nrtri.out");

    int n, i, j, x, tri = 0;
    cin>>n;
    for(i = 1; i <= n; i++)
        cin>>a[i];

    sort(a + 1, a + n + 1);

    int temp;

    for(i = 1; i <= n-2; i++) {
        for(j = i+1; j <= n-1; j++) {
            temp = 0;
            x = a[i] + a[j];
            if(x >= a[n]) {
                tri += n - j;
                continue;
            } else if (x >= a[j+1]) {
                cbin(j+1, n, x, temp);
                tri += temp - j;
            }
        }
    }

    cout<<tri;

    return 0;
}