Cod sursa(job #2959238)

Utilizator gabrielstefanStefan Gabriel gabrielstefan Data 30 decembrie 2022 12:06:41
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, a[1001], cnt;
int bin(int s, int st, int dr){
    if(s >= a[n])
        return n;
    if(s < a[st])
        return st - 1;
    int m, p;
    while(st <= dr){
        m = (st + dr) / 2;
        if(a[m] <= s){
            p = m;
            st = m + 1;
        }
        else
            dr = m - 1;
    }
    return p;
}

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

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

    for(int i = 1; i <= n - 2; ++i){
        for(int j = i + 1; j <= n - 1; ++j){
            int st = j + 1, dr = n;
            int s = a[i] + a[j];
            cnt += bin(s, st, dr) - st + 1;
        }
    }

    cout << cnt;

    return 0;
}