Cod sursa(job #2589313)

Utilizator GligarEsterabadeyan Hadi Gligar Data 26 martie 2020 09:45:23
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>

using namespace std;

ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

const int nmax=800;

int v[nmax+1];

int main(){
    int n;
    fin>>n;
    int n2=1;
    while(n2<=n){
        n2*=2;
    }
    n2/=2;
    for(int i=1;i<=n;++i){
        fin>>v[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;++j){
            if(v[i]>v[j]){
                int a=v[i];
                v[i]=v[j];
                v[j]=a;
            }
        }
    }
    int sol=0;
    for(int i=1;i<=n-2;++i){
        for(int j=i+1;j<=n-1;++j){
            int p=j;
            for(int k=n2;k>=1;k/=2){
                if(p+k<=n&&v[p+k]<=v[i]+v[j]){
                    p+=k;
                }
            }
            sol+=p-j;
        }
    }
    fout<<sol<<"\n";
    return 0;
}