Cod sursa(job #2384604)

Utilizator alezizalex artene aleziz Data 20 martie 2019 22:04:08
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("nrtri.in");
ofstream cout ("nrtri.out");

int v[802];
int main()
{
    int n,sol = 0;
    cin >> n;
    for (int i =1; i<= n; ++i)
    {
        cin >> v[i];
    }
    sort (v + 1,v + n + 1);
    for (int i =1; i<= n; ++i)
    {
        int k = v[i];
        for (int j = i + 1; j <= n; ++j)
        {
            int s = v[j];
            int st = j + 1;
            int dr = n;
            int h = j;
            while (st <= dr)
            {
                int mid = (st + dr) / 2;
                if (k + s >= v[mid])
                {
                    st = mid + 1;
                    h = mid;
                }
                else
                    dr = mid - 1;
            }
            sol += h - j;
        }
    }
    cout << sol;
    return 0;
}