Cod sursa(job #2664821)

Utilizator RazvanLazar2004Lazar Razvan Gabriel RazvanLazar2004 Data 29 octombrie 2020 15:27:03
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include<algorithm>
using namespace std;
int v[801];
int main()
{
    ifstream in("nrtri.in");
    ofstream out("nrtri.out");
    long long int n,l=0,t=1;
    in>>n;
    while(t*2<=n){
        t*=2;
    }
    for(long long int i=1;i<=n;i++){
        in>>v[i];
    }
    sort(v+1,v+n+1);
    for(long long int i=1;i<=n-2;i++){
        for(long long int j=i+1;j<=n-1;j++){
            long long int a=v[i]+v[j];
            if(a<v[n]){
                long long int r=0;
                for(long long int k=t;k>0;k/=2){
                    if(v[r+k]<=a && r+k<=n){
                        r+=k;
                    }
                }
                l+=(r-j);
            }else{
                l+=(n-j);
            }
        }
    }
    out<<l;
}