Cod sursa(job #590589)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 18 mai 2011 17:43:43
Problema Numarare triunghiuri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream.h>
long a[801],b[801],nr=0;
int i,j,k,n;
void merge(long a[801],int p,int q)
{int m=(p+q)/2,i,j,k;
if(p==q)
     return;
merge(a,p,m);
merge(a,m+1,q);
for(i=p,j=m+1,k=p;i<=m||j<=q;)
if(j>q||(i<=m&&a[i]<a[j]))
       b[k++]=a[i++];
else
       b[k++]=a[j++];
for(i=p;i<=q;i++)
       a[i]=b[i];}
int main()
{ifstream f("nrtri.in");
ofstream g("nrtri.out");
f>>n;
for(i=1;i<=n;i++)
      f>>a[i];
merge(a,1,n);
for(i=1;i<n-1;i++)
      {for(j=i+1;j<n;j++)
              {k=j+1;
              while(a[i]+a[j]>=a[k]&&k<=n)
                     k++;
              nr+=k-j-1;}}
g<<nr;
f.close();
g.close();
return 0;}