Cod sursa(job #1283290)

Utilizator sebiinfosimon sebastian sebiinfo Data 5 decembrie 2014 14:58:47
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>

using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");
const int nmax=800;
int a[nmax+1],v[nmax+1];

void mergesort (int i,int j)
{
    int p=i,q=(i+j)/2+1;
    if(i==j)
    return ;
    mergesort(i,(i+j)/2);
    mergesort((i+j)/2+1,j);
    for(int x=i;x<=j;x++)
    {
        if( q>j || (p<=(i+j)/2 && v[p]<v[q]) )
        {
            a[x]=v[p];
            p++;
        }
        else
        {
            a[x]=v[q];
            q++;
        }
    }
    for(int x=i; x<=j;x++)
    v[x]=a[x];
}

int main()
{
    int n,i,j,s=0,x,sol;
    in>>n;
    for(i=1;i<=n;i++)
    in>>v[i];
    mergesort(1,n);
    for(i=1;i<=n-2;i++)
        for(j=i+1;j<=n-1;j++)
        {
            for(x=1;x<=n;x*=2){
            }
            sol=j+1;
            for(int step=x;step>0;step/=2)
            {
                if(sol+step<=n && v[sol+step]<=v[i]+v[j])
                    sol+=step;
            }
            if(v[sol]<=v[i]+v[j])
            s+=sol-j;
        }
    out<<s;
    return 0;
}