I have tried new method using merge sort . Its complexity is O(n)+O(nlogn)
But it gives runtime error in 9th test case . What should i do
#include<stdio.h>
void merge(long long a[], long long low, long long high, long long mid);
int mergesort(long long a[], long long low,long long high)
{
long long mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return(0);
}
void merge(long long a[], long long low, long long high, long long mid)
{
long long i, j, k, c[200000];
i=low;
j=mid+1;
k=low;
while((i<=mid)&&(j<=high))
{
if(a[i]<a[j])
{
c[k]=a[i];
k++;
i++;
}
else
{
c[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
c[k]=a[i];
k++;
i++;
}
while(j<=high)
{
c[k]=a[j];
k++;
j++;
}
for(i=low;i<k;i++)
{
a[i]=c[i];
}
}
int main()
{
long long i,j=0,n=0,m=0,min,sum=0L;
scanf("%lld %lld",&n,&m);
long long a[n],b[n];
for(i=0;i<n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
}
mergesort(a,0,n-1);
long long sub=0L;
for(i=0;i<n;i++)
{
min=a[i]-sub;
if((sum-(n-i)*min)>m)
sub=a[i];
if((sum-(n-i)*min)==m)
{ sub=a[i];
break;
}
if((sum-(n-i)*min)<m)
{ sub+=(sum-m)/(n-i);
break;
}
a[i]-=sub;
sum-=(n-i)*min;
}
printf("%lld\n",sub);
return 0;
}