Cod sursa(job #2516876)

Utilizator WilIiamperWilliam Damian Balint WilIiamper Data 2 ianuarie 2020 15:32:29
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin ("nrtri.in");
ofstream fout ("nrtri.out");
int n, b[1001], nr;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> b[i];

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

    for (int i = 1; i < n; i++) {
        for (int j = i+1; j < n; j++) {

            int st = j+1, dr = n, s = b[i]+b[j], mid;
            while (st <= dr) {
                mid = st + (dr-st)/2;
                if (b[mid] > s)
                    dr = mid-1;
                else if (b[mid] < s)
                    st = mid+1;
                else {
                    dr = mid;
                    break;
                }
            }
            while (b[dr+1] <= s && dr+1 <= n)
                dr++;

            nr += (dr - j);
        }
    }
    fout << nr;
    return 0;
}