stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

using namespace std;

int main(){

  int N, A, B;

  int count = 0;

  scanf("%d %d %d", &N, &A, &B);

  if(N == 1){

    if(A == B) printf("1");

    else printf("0");

  } else {

    if(A > B){

      printf("0");

    } else {

      printf("%lld", (long long)(B-A)*(N-2)+1);

    }

  }

  return 0; 

}

// Optimized solution to the same problem (faster):
#include <cstdio>



int main()

{

    int A,B,N;

    scanf("%d%d%d",&N,&A,&B);

    if(N==1)

    {

        if(A==B)

            printf("1\n");

        else

            printf("0\n");

    }

    else

    {

        if(A>B)

            printf("0\n");

        else

            printf("%lld\n",(long long )(B-A)*(N-2)+1);

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}

inline void getInt(int* p);

const int maxn=1000010;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/



int main()

{

	// freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);

    int n,a,b;

    while(cin>>n>>a>>b)

    {

    	if(n==1)

    	{

    		if(a!=b)

    		{

    			cout<<0<<endl;

    		}else

    		{

    			cout<<1<<endl;

    		}

    	}else

    	{

    		if(a<=b)

    		{

    			if(n==2)

    			{

    				cout<<1<<endl;

    				continue;

    			}

    			ll ans=1ll*(n-2)*b-1ll*(n-2)*a+1ll;

    			cout<<ans<<endl;

    		}else

    		{

    			cout<<0<<endl;



    		}

    	}

    }

    return 0;

}



inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '0');

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 - ch + '0';

        }

    }

    else {

        *p = ch - '0';

        while ((ch = getchar()) >= '0' && ch <= '9') {

            *p = *p * 10 + ch - '0';

        }

    }

}




// Optimized solution to the same problem (faster):
#include <cstdio>



int main()

{

    int A,B,N;

    scanf("%d%d%d",&N,&A,&B);

    if(N==1)

    {

        if(A==B)

            printf("1\n");

        else

            printf("0\n");

    }

    else

    {

        if(A>B)

            printf("0\n");

        else

            printf("%lld\n",(long long )(B-A)*(N-2)+1);

    }

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <utility>

#include <numeric>

using namespace std;

//変数デバッグ

#define DEB(variable) cout << #variable << '=' << variable << endl



//for簡易表記(引数ミス防止)

#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)

#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)





int main(){



    long long int n,a,b;

    cin>>n>>a>>b;

    if(n==0||(n==1&&a!=b)||a>b){

        cout << 0 << endl;

    }else{

        cout << 1 + ((n - 2) * (b - a)) << endl;

    }

    return 0;

}   

// Optimized solution to the same problem (faster):
#include <cstdio>



int main(void)

{

    int A,B,N;

    scanf("%d%d%d",&N,&A,&B);

    if(N==1)

    {

        if(A==B)

            printf("1\n");

        else

            printf("0\n");

    }

    else 

    {

        if(A>B)

            printf("0\n");

        else

            printf("%lld\n",(long long )(B-A)*(N-2)+1);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;



int main(){

	long long n,a,b;cin >> n >> a >> b;

	

	long long count=0;

	if(n==1&&a==b) cout << "1";

	else if(n==1&&a!=b) cout << "0";

	else if(a>b) cout << "0";

	else {

		count=(n-2)*b-(n-2)*a+1;

		cout << count;

	}

	

	return 0;

} 

// Optimized solution to the same problem (faster):
#include <cstdio>



int main(void)

{

    int A,B,N;

    scanf("%d%d%d",&N,&A,&B);

    if(N==1)

    {

        if(A==B)

            printf("1\n");

        else

            printf("0\n");

    }

    else 

    {

        if(A>B)

            printf("0\n");

        else

            printf("%lld\n",(long long )(B-A)*(N-2)+1);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <vector>

#include <list>

#include <climits>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <cmath>

#include <regex>

using namespace std;



int main()

{

long long n,a,b;

cin>>n>>a>>b;

if(n==1&&a==b)

{

    cout<<1;

    return 0;

}

if(n<2||a>b)

{

    cout<<0;

    return 0;

}

cout<<(b-a)*(n-2)+1;



}


// Optimized solution to the same problem (faster):
#include <cstdio>



int main(void)

{

    int A,B,N;

    scanf("%d%d%d",&N,&A,&B);

    if(N==1)

    {

        if(A==B)

            printf("1\n");

        else

            printf("0\n");

    }

    else 

    {

        if(A>B)

            printf("0\n");

        else

            printf("%lld\n",(long long )(B-A)*(N-2)+1);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5+10;

int a[maxn];

int cmp(const int a,const int b){return a>b;}

int n,m,v,p,b[maxn];

bool check(int mid)

{

    if(mid<=p)return 1;

    if(a[mid]+m<a[p])return 0;

    if(v<=p-1&&a[mid]+m>=a[p])return 1;

    for(int i=1;i<=n;i++)b[i]=a[i];

    int temp=0;

    for(int i=1;i<=p-1;i++)b[i]+=m,temp+=m;

    int inx=n,cnt=v-p+1;

    while(inx>mid&&cnt>1)temp+=m,inx--,cnt--,b[inx]+=m;

    temp+=m;

    int now=a[mid]+m;

    int res=m*v-temp;

    for(int i=p;i<mid;i++)

	{

        int add=min(m,max(now-a[i],0ll));

        if(add>res)add=res;

        res-=add,b[i]+=add;

    }

    return now>=b[p]&&res<=0;

}

signed main()

{

    cin>>n>>m>>v>>p;

    for(int i=1;i<=n;i++)cin>>a[i];

    sort(a+1,a+n+1,cmp);

    int l=1,r=n;

    int ans=0;

    while(l<=r)

	{

        int mid=(l+r)>>1;

        if(check(mid))l=mid+1,ans=mid;

        else r=mid-1;

    }

    cout<<ans<<endl;

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#define ll long long

using namespace std;

const int N=1e5+5;

int n,m,v,p;

ll a[N],sum[N];

bool check(int x){

	if(a[x]+m<a[p]) return 0;

	return 1ll*m*v<=1ll*(p-1ll)*m+1ll*(n-x+1)*m-1ll*(sum[x-1]-sum[p-1])+1ll*(a[x]+m)*(x-p);

}

signed main() {

	scanf("%d%d%d%d",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+n+1);

	reverse(a+1,a+n+1);

	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

	int l=p,r=n,ans=p;

	while(l<=r){

		int mid=l+r>>1;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	printf("%d\n",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define int long long

using namespace std;

int num[100007],chance=0,n,m,v,p;

bool cmp(int a,int b)

{

	return a>b;

}

signed main() 

{

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	int ans=p;

	for(int i=1;i<=n;i++)

	{

		scanf("%lld",&num[i]);

	}

	sort(num+1,num+1+n,cmp);

	for(int i=1;i<=n-p;i++)

	{

		if(num[p]>num[p+i]+m)

		{

			cout<<ans<<endl;

			return 0;

		}

		int t=v+i-n;

		if(t<=0)

		{

			ans++;

		}

		else 

		if( (t*m-chance-1)/i +num[p]+1<=num[p+i]+m)

		{

			ans++;

		}

		chance+=num[p]-num[p+i];

//		cout<<ans<<' ';

	}

	cout<<ans<<endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#define ll long long

using namespace std;

const int N=1e5+5;

int n,m,v,p;

ll a[N],sum[N];

bool check(int x){

	if(a[x]+m<a[p]) return 0;

	return 1ll*m*v<=1ll*(p-1ll)*m+1ll*(n-x+1)*m-1ll*(sum[x-1]-sum[p-1])+1ll*(a[x]+m)*(x-p);

}

signed main() {

	scanf("%d%d%d%d",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+n+1);

	reverse(a+1,a+n+1);

	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

	int l=p,r=n,ans=p;

	while(l<=r){

		int mid=l+r>>1;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	printf("%d\n",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

long long n, m, v, p, a[100001];

bool cmp(long long x, long long y)

{

    return x > y;

}

int main(int argc, char const *argv[])

{

    scanf("%lld%lld%lld%lld", &n, &m, &v, &p);

    for (int i = 1; i <= n; i++)

    {

        scanf("%lld", &a[i]);

    }

    sort(a + 1, a + n + 1, cmp);

    long long ans = p, sum = 0;

    for (int i = p + 1; i <= n; i++)

    {

        if (a[i] + m < a[p])

        {

            break;

        }

        if (v - n + i <= p)

        {

            ans++;

        }

        else

        {

            if (((v - p - n + i) * m - sum - 1) / (i - p) + 1 + a[p] <= a[i] + m)

            {

                ans++;

            }

        }

        sum += a[p] - a[i];

    }

    printf("%lld\n", ans);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#define ll long long

using namespace std;

const int N=1e5+5;

int n,m,v,p;

ll a[N],sum[N];

bool check(int x){

	if(a[x]+m<a[p]) return 0;

	return 1ll*m*v<=1ll*(p-1ll)*m+1ll*(n-x+1)*m-1ll*(sum[x-1]-sum[p-1])+1ll*(a[x]+m)*(x-p);

}

signed main() {

	scanf("%d%d%d%d",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+n+1);

	reverse(a+1,a+n+1);

	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

	int l=p,r=n,ans=p;

	while(l<=r){

		int mid=l+r>>1;

		if(check(mid)){

			ans=mid;

			l=mid+1;

		}

		else r=mid-1;

	}

	printf("%d\n",ans);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



typedef long long ll;

const int N=1e5+10;



int n,m,v,p;

int a[N];



bool check(int mid){

	ll ans=0;

	if(a[mid]+m<a[p]) return false;

	for(int i=1;i<=n;i++){

		if(i>=p&&i<mid) ans+=(ll)(a[mid]+m-a[i]);

		else ans+=(ll)m;

	}

//	cout<<' '<<ans<<endl; 

	if((ll)m*(ll)v>ans) return false;

	return true;

}



bool cmp(int a,int b){

	return a>b;

}



int main(){

	cin.tie(0);

	cin>>n>>m>>v>>p;

	for(int i=1;i<=n;i++) cin>>a[i];

	sort(a+1,a+n+1,cmp);

	int l=1,r=n;

	while(l<r){

		int mid=(l+r+1)>>1;

		if(mid<=p) l=mid;

		else if(check(mid)) l=mid;

		else r=mid-1;

//		cout<<l<<' '<<r<<' ';

//		cout<<check(mid)<<endl;

	}

	cout<<l<<endl;

	return 0;

}

/*

	while(r>=l){

        mid=(r+l)>>1;

       // cout << "*******" << '\n';

        ll z=check(mid);

        if(z<m)

        r=mid-1;

        else{

            l=mid+1;

        }

    }

*/

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;

using ll = long long;

int n, m, v, p;

const int maxn = 1e5+7;

vector<ll>a;

ll pre[maxn];

int main()

{

	ios::sync_with_stdio(false);cin.tie(0);

	cin >> n >> m >> v >> p;

	a.resize(n);

	for(auto &u:a){

		cin >> u;

	}

	sort(a.begin(), a.end(), [&](int a, int b){

		return a > b;

	});

	for(int i=0; i<n; ++i){

		pre[i+1] = pre[i]+a[i];

	}

	ll ans = p;

	for(int i=p; i<n; ++i){

		if(a[i]+m<a[p-1])break;

		ll cur = v-(n-(i-p+1));//需要超过的人里的投票数 

		if(cur<=0){//全给不会产生影响的人投票 

			ans++;

			continue;

		}

		if(cur*m<=(i-p+1)*(a[i]+m)-(pre[i]-pre[p-1]))ans++;//需要超过的人里投票 

	}

	cout << ans; 

} 

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;



int n, m, v, w;

vector<int> a, p;



bool chk(int x){

        if (x + w >= n) return true;

        int r = v - w - x;

        if (r < 0) {

            for (int i = x + 1; i + w <= n; ++i)

                if (a[p[x]] + m < a[p[i]]) return false;

            return true;

        }

        else {

            ll s = 1ll * r * m;

            for (int i = x + 1; i + w <= n; ++i) {

                int y = a[p[x]] + m - a[p[i]];

                if (y > 0)

                    s -= a[p[x]] + m - a[p[i]];

                else if (y < 0)

                    return false;

            }

            return s <= 0;

        }

    }



int main(void) {

    scanf("%d%d%d%d", &n, &m, &v, &w);

    a.resize(n, 0);

    p.resize(n, 0);

    for (int& i : a) scanf("%d", &i);

    iota(p.begin(), p.end(), 0);

    sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });



    int l = 0, r = n - 1;

    while (l <= r) {

        int mid = (l + r) >> 1;

        if (chk(mid)) r = mid - 1;

        else l = mid + 1;

    }





    printf("%d\n", n - l);

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<stdio.h>

#include<cstdio>

#include<vector>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#include<string>

#include<stack>

#include<set>

#include<map>

#include<time.h>

#include<cstdlib>

typedef long long ll;

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#define mm(a) memset(a,0,sizeof(a))

#define lr rt<<1

#define rr rt<<1|1

#define sync std::ios::sync_with_stdio(false);std::cin.tie(0);

#define inf 0x3f3f3f3f

#define eqs 1e-8

#define lb(x) (x&(-x))

#define ch(a) (int(a-'a')+1)

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef pair<int,int> pii;

const double pi=acos(-1);

const int maxn=100005;

const ll Mod=1000000007;





ll a[maxn];

bool cmp(ll a,ll b)

{

    return a>b;

}



int main()

{

    sync;

    ll n,m,v,p;

    cin>>n>>m>>v>>p;

    for(int i=1;i<=n;i++)

    {

        cin>>a[i];

    }

    sort(a+1,a+n+1,cmp);

    ll d=a[p];

    int sum=0;

    ll s=0;

    ll c=0;

    for(int i=p;i<=n;i++)

    {

        if(a[i]>d)

        {

            sum++;

            continue;

        }

        if(d-m>a[i])

            break;

        if(s<=1ll*(n-v)*m+1ll*a[i]*c)

        {

            sum++;

            s+=a[i];

            c++;

        }

        else

            break;

    }

    cout<<sum+p-1<<endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define m_k make_pair

#define int long long

using namespace std;

const int N=1e5+100;

int n,m,v,p,a[N],sum[N],ans;

signed main()

{

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for (int i=1;i<=n;i++) scanf("%lld",&a[i]);

	sort(a+1,a+1+n);

	for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

	a[n+1]=inf;

	for (int i=n;i>=1;i--)

	{

		if (i>=v)

		{

			int pos=upper_bound(a+1,a+2+n,a[i]+m)-a;

			if (n-pos+1<p) ans++;

		}

		else

		{

			int pos=upper_bound(a+1,a+2+n,a[i]+m)-a;

			if (n-pos+1>=p) continue;

			if (v-i-p+1<=0)

			{

				ans++;

				continue;

			}

			int cnt=v-i-p+1;

			int l=i+1,r=min(n-p+1,pos-1);

			if (r-l+1>=cnt && cnt*m<=(a[i]+m)*(r-l+1)-(sum[r]-sum[l-1])) ans++;

		}

	}

	printf("%lld\n",ans);

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,v,p,s,mx,c,r,b,a[100005];

signed main()

{

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++) scanf("%lld",a+i);

	sort(a+1,a+n+1),c=a[n-p+1],b=0,r=p,v=n-v,s=0,mx=0;

	for(int i=n;i>=1;i--) if(a[i]<c) break;else b++;

	for(int i=n-p;i>=1;i--)

	{

		s+=(a[i+1]-a[i])*(n-p+1-i);

		if(s<=min(n-p,v)*m&&a[n-p+1]-a[i]<=m) r++;else break;

	}

	return printf("%lld\n",r),0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <vector>

#include <stack>

#include <map>

#define ri register

#define inf 0x7fffffff

#define E (1)

#define mk make_pair

#define int long long

using namespace std; const int N=200010;

inline int read()

{

	int s=0, w=1; ri char ch=getchar();

	while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar(); return s*w;

}

int n,m,v,p,a[N],now,res;

inline bool cp(int x,int y) { return x>y; }

signed main()

{

	n=read(), m=read(), v=read(), p=read();

	for(ri int i=1;i<=n;i++) a[i]=read();

	sort(a+1,a+1+n,cp); now=p;

	for(ri int i=p+1;i<=n;res+=a[p]-a[i], i++)

	{

		if(a[p]>a[i]+m) break; // m 次全部加上去还不如别人不加

		if(p-1+n-i+1>=v || ((v-(p-1+n-i+1))*m-res-1)/(i-p)<=a[i]-a[p]-1+m) now++;// 否则把数都加给 i 和后面以及 p-1 和前面

		// 还有一种情况，还得给 p 到 i-1 这里放，那么尽量使得放了之后平均最小即可。 

	} printf("%lld\n",now);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>



const int maxn=1e5+5;

#define int long long

int n,m,v,p,last,a[maxn];



inline bool cmp(int a,int b){

	return a>b;

}



inline int max(int a,int b){

	return a>b?a:b;

}



inline bool check(int x){

	if(x<=p) return true;

	if(a[x]+m<a[p]) return false;

	int now=m*(p-1+n-x+1);

	for(int i=p+1;i<x;i++){

		now+=a[x]+m-a[i];

	}now+=a[x]+m-a[p];

	return now>=m*v;

}



signed main(){

	scanf("%lld%lld%lld%lld",&n,&m,&v,&p);

	for(int i=1;i<=n;i++){scanf("%lld",&a[i]);}

	std::sort(a+1,a+n+1,cmp);

	int l=1,r=n,mid,pos=p;

	while(l<=r){

		mid=(l+r)>>1;

		if(check(mid)){

			l=mid+1;

			pos=mid;

		}else r=mid-1;

	}

	printf("%lld\n",pos);

	return 0;

}

// Fastest known solution for this problem: