Cod sursa(job #2896107)

Utilizator erixEric stoicescu erix Data 29 aprilie 2022 20:00:15
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("nrtri.in");
ofstream cout("nrtri.out");
int main(){
    int n;
    cin >> n;
    int* arr = new int[n];
    for (int i = 0; i < n;i++){
        int x;
        cin >> x;
        arr[i] = x;
    }
    sort(arr,arr+n);
    int cnt = 0;
    int sum = 0;
    for (int i = 0; i < n-2;i++){
        for (int j = i + 1; j < n-1;j++){
            sum = arr[i] + arr[j];
            ///search with binary search for v[k]<=sum<=v[k+1] and increase cnt with n-k
            int st = j + 1, dr = n - 1, k = 0;
            while(st<=dr){
                int mij = (st + dr) / 2;
                if(arr[mij]<=sum){
                    st = mij + 1;
                    k = mij;
                }
                else dr = mij - 1;
            }
            if(k!=0)
                cnt += k - j;
        }
    }
    cout << cnt;
    return 0;
}