Cod sursa(job #3228507)

Utilizator CalinHanguCalinHangu CalinHangu Data 8 mai 2024 16:02:21
Problema Numarare triunghiuri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second
#define ll long long
#define pb push_back
#define bg begin()
#define ed end()
#define cl clear()
#define pii pair<int, int>

#define int ll

using namespace std;

ifstream in("nrtri.in");
ofstream out("nrtri.out");

const int MOD = 1e9 + 7;
const char nl = '\n';
const int NMAX = 1e5 + 5;
const int INF = 1e9;

int n, v[NMAX];

signed main()
{
    int cnt = 0, ans = -1, l, r;
    in >> n;
    for(int i = 1; i <= n; ++i)
        in >> v[i];
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){
            l = j + 1, r = n, ans = -1;
            while(l <= r)
            {
                int mid = (l + r) / 2;
                if(v[i] + v[j] >= v[mid]){
                    ans = mid;
                    l = mid + 1;
                }
                else
                    r = mid - 1;
            }
            if(ans > 0)
                cnt++;
        }
    }
    out << cnt << nl;
    return 0;
}