Cod sursa(job #3144958)

Utilizator addanciuAdriana Danciu addanciu Data 11 august 2023 16:07:09
Problema Numarare triunghiuri Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
//#define CONSOLE /// daca ai in consola

using namespace std;

basic_ifstream<char> fin("nrtri.in");
basic_ofstream<char> fout("nrtri.out");

#ifdef CONSOLE
    #define fin cin 
    #define fout cout 
#endif
int v[800];
bool verify(int number,int a,int b){
    if(v[a]+v[b]>=number) return true;
    return false;
}

int main() {
    int n,x,nr=0;
    fin>>n;
    for(int i=1;i<=n;i++){
        fin>>v[i];
    }
    sort(v+1,v+n+1);
    for(int i=1;i+1<n;i++){
        for(int j=i+1;j<n;j++){
            int left=1,right=n,ans=0;
            while(left<=right){
                int middle=(left+right)/2;
                if(verify(v[middle],i,j))left=middle+1,ans=middle;
                else right=middle-1;
            }
            nr+=ans-j;
        }
    }
    fout<<nr;
    return 0;
}