제출 #106976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106976		hugo_pm	구경하기 (JOI13_watching)	C++17	50 / 100	1071 ms	11904 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 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; }
		int lim = pos[cr] + longueur;
		auto it = lower_bound(pos.begin(), pos.end(), lim);
		int ncr = it - pos.begin();
		assert(ncr >= cr);
		chmax(rep, ncr);
	}

	if (big) {
		int cr = dp[small][big-1];
		if (cr >= nbEv) { rep = cr; return; }
		int lim = pos[cr] + 2*longueur;
		auto it = lower_bound(pos.begin(), pos.end(), lim);
		int ncr = it - pos.begin();
		assert(ncr >= cr);
		chmax(rep, ncr);
	}
}

bool ok(int longueur)
{
	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: 0 / 50