Cod sursa(job #2982422)

Utilizator JungwonPreppy Girl Jungwon Data 20 februarie 2023 11:54:03
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <bits/stdc++.h>

using namespace std;

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

int cb(int st, int dr, int v[], int s)
{
    int k=0,mj=0,poz=0,j=st-1;
    while(st<=dr)
    {
        mj=(st+dr)/2;
        if(v[mj]<=s)
            poz=mj,st=mj+1;
        else
            dr=mj-1;
    }
    if(poz)
        return poz-j;
    return 0;
}
int n,s,v[100001],k;
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];
    sort(v+1,v+n+1);
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            s=v[i]+v[j];
            k=k+cb(j+1,n,v,s);
        }
    }
    g<<k;
    return 0;
}