Codeforces 1133C. Balanced Team Codeforces Round #544 (Div. 3)

two pointer Zinnatul Islam Morol Saturday, March 09, 2019

Problem link

Let's sort all values in non-decreasing order. Then we can use two pointers to calculate for each student i the maximum number of students j such that aj−ai≤5 (j>i). This is pretty standard approach. We also can use binary search to do it (or we can store for each programming skill the number of students with this skill and just iterate from some skill x to x+5 and sum up all numbers of students).

A solution in c++

	#include<bits/stdc++.h>

	using namespace std;

	/// Typedef
	typedef long long ll;

	#define sc1(a) scanf("%lld",&a)
	#define sc2(a,b) scanf("%lld %lld",&a,&b)

	#define pf1(a) printf("%lld\n", a)
	#define pf2(a,b) printf("%lld %lld\n",a,b)

	#define mx 1000000
	#define mod 1000000007
	#define PI acos(-1.0)

	#define size1 200005

	int drx[8] = {-2,-2,-1,-1,1,1,2,2};
	int dcy[8] = {-1,1,-2,2,-2,2,-1,1};

	int dirx[4] = { -1, 0, 1, 0 };
	int diry[4] = { 0, -1, 0, 1 };

	ll gcd(ll a,ll b){ if(b == 0) return a; return gcd(b, a % b); }
	ll lcm(ll a,ll b){return a/gcd(a,b)*b;}


	vector <ll> vc;

	int main()
	{
	// seive();

	ll tc, num, t = 1, pownum;

	//freopen("/opt/Coding/clion code/input.txt", "r", stdin);
	//freopen("/opt/Coding/clion code/output.txt", "w", stdout)


	sc1(num);

	for(ll i = 0; i < num; i++){
	ll x;
	sc1(x);
	vc.push_back(x);
	}

	sort(vc.begin(), vc.end());

	ll ans = 0;
	for(ll i = 0; i < num; i++){
	ll now = upper_bound(vc.begin(), vc.end(), vc[i] + 5) - (vc.begin() + i);
	ans = max(ans, now);
	}

	pf1(ans);

	return 0;
	}