Submission #106977

#	Time	Username	Problem	Language	Result	Execution time	Memory
106977		hugo_pm	Watching (JOI13_watching)	C++17	100 / 100	142 ms	11896 KiB

watching

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

void solve();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}

const int borne = 2005;
vector<int> pos;
int gt[borne][2];
int dp[borne][borne];
int nbEv, nbPetits, nbGrands;

void comp(int small, int big, int longueur)
{
	int &rep = dp[small][big];
	rep = 0;

	if (small) {
		int cr = dp[small-1][big];
		if (cr >= nbEv) { rep = cr; return; }
		chmax(rep, gt[cr][0]);
	}

	if (big) {
		int cr = dp[small][big-1];
		if (cr >= nbEv) { rep = cr; return; }
		chmax(rep, gt[cr][1]);
	}
}

void cp(int longueur, int vers)
{
	int i = 0, j = 0;
	while (i < nbEv) {
		while (j < nbEv && pos[j] < pos[i]+longueur) ++j;
		gt[i][vers] = j;
		++i;
	}
}

bool ok(int longueur)
{
	cp(longueur, 0); cp(2*longueur, 1);
	form(smallUsed, nbPetits+1) form(bigUsed, nbGrands+1) {
		if (smallUsed + bigUsed >= 1) {
			comp(smallUsed, bigUsed, longueur);
		}
	}
	return (dp[nbPetits][nbGrands] >= nbEv);
}
void solve()
{
	cin >> nbEv >> nbPetits >> nbGrands;
	pos.resize(nbEv);
	form(i, nbEv) cin >> pos[i];
	sort(pos.begin(), pos.end());

	if (nbPetits + nbGrands >= nbEv) {
		cout << "1\n";
		return;
	}

	int l = 1, r = (int)(1e9) + 5;
	while (l < r) {
		int m = (l+r) / 2;
		if (ok(m)) r = m;
		else l = m+1;
	}
	cout << l << "\n";
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50