Cod sursa(job #2064431)

Utilizator TheNextGenerationAyy LMAO TheNextGeneration Data 12 noiembrie 2017 12:54:41
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");
int v[805];
int main()
{
    ios::sync_with_stdio(0);
    in.tie(0);
    out.tie(0);
    int n,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; j++)
        {
            int st = j+1, dr = n;
            while (st<=dr)
            {
                int mj = (st+dr)/2;
                if (v[mj]>v[i]+v[j])
                    dr = mj-1;
                else
                    st = mj+1;
            }
            nr+=st-j-1;
        }
    out << nr;
}