Pagini recente » Istoria paginii runda/oji2012blabla/clasament | Cod sursa (job #394260) | Cod sursa (job #1670798) | Istoria paginii runda/tema_vacanta_sambata_14.30/clasament | Cod sursa (job #520209)
Cod sursa(job #520209)
#include <stdio.h>
#include <string>
FILE *fin = fopen("nrtri.in","r");
FILE *fout= fopen("nrtri.out","w");
int i,j,N,NR;//v[805],id[805];
int v[1<<10],id[1<<10];
char s[8000];
void citire()
{
fscanf(fin,"%d\n",&N);
fgets(s,sizeof(s),fin);
int L=strlen(s),p=0;
for(i=0;i<=L;i++)
{
for(;s[i]==' ' && i<=L;i++);
if(i==L) break;
p++;
for(;s[i]>='0'&&s[i]<='9'&&i<=L;i++)
v[p]=10*v[p]+s[i]-'0';
}
}
void mergesort(int st, int m, int dr)
{
int aux[m-st+2],i,j,k;
i=1; j=st;
while(j<=m)
aux[i++]=id[j++];
i=1; k=st;
while(j<=dr && k<j)
if(v[aux[i]]<=v[id[j]])
id[k++]=aux[i++];
else
id[k++]=id[j++];
while(k<j)
id[k++]=aux[i++];
}
void msort(int st, int dr)
{
if(st<dr)
{
int m=st-(st-dr)/2;
msort(st,m);
msort(m+1,dr);
mergesort(st,m,dr);
}
}
int cb(int st, int dr)
{
int m=st-(st-dr)/2;
while(st<=dr)
{
if((v[id[m]]<=v[id[i]]+v[id[j]]&&v[id[m+1]]>v[id[i]]+v[id[j]]) || (m==N && v[id[m]]<=v[id[i]]+v[id[j]]))
return m;
else if(v[id[m]]<=v[id[i]]+v[id[j]])
st=m+1;
else dr=m-1;
m=st-(st-dr)/2;
}
return 0;
}
void rez()
{
for(i=1;i<=N-2;i++)
for(j=i+1;j<=N-1;j++)
{
int p=cb(j+1,N);
for(;p>=j+1;p--) NR++;
}
}
int main()
{
citire();
for(i=1;i<=N;i++) id[i]=i;
msort(1,N);
rez();
fprintf(fout,"%d",NR);
}