Cod sursa(job #398212)

Utilizator DraStiKDragos Oprica DraStiK Data 18 februarie 2010 11:19:12
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <algorithm>
using namespace std;

#define DIM 1030

struct sume {int s,i,j;} sum[DIM*DIM];
int c,l,m,nrt;
int a[DIM];

void read ()
{
    int i;

    scanf ("%d%d",&c,&l);
    for (i=1; i<=c; ++i)
        scanf ("%d",&a[i]);
}

struct cmp
{
    bool operator () (const sume &a,const sume &b)
    {
        return a.s<b.s;
    }
};

void cbin (int suma,int i1,int i2)
{
    int st,dr,mij;

    for (st=1, dr=m; st<=dr; )
    {
        mij=(st+dr)/2;
        if (sum[mij].s==suma)
        {
            for (st=mij; sum[st].s==suma; --st)
                if (sum[st].i>i1 && sum[st].j>i2 && sum[st].i>i2 && sum[st].j>i1)
                    ++nrt;

            for (dr=mij+1; sum[dr].s==suma; ++dr)
                if (sum[dr].i>i1 && sum[dr].j>i2 && sum[dr].i>i2 && sum[dr].j>i1)
                    ++nrt;
            return ;
        }
        else if (sum[mij].s<suma)
            st=mij+1;
        else
            dr=mij-1;
    }
}

void solve ()
{

    int i,j,i1,i2,suma;

    for (i=1; i<c; ++i)
        for (j=i+1; j<=c; ++j)
        {
            ++m;
            sum[m].s=a[i]+a[j];
            sum[m].i=i;
            sum[m].j=j;
        }
    sort (sum+1,sum+m+1,cmp ());
    for (i=1; i<=m; ++i)
    {
        suma=l-sum[i].s;
        i1=sum[i].i;
        i2=sum[i].j;
        cbin (suma,i1,i2);
    }
    printf ("%d",nrt);
}

int main ()
{
    freopen ("oite.in","r",stdin);
    freopen ("oite.out","w",stdout);

    read ();
    solve ();

    return 0;
}