답안 #106977

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106977 2019-04-21T11:13:43 Z hugo_pm 구경하기 (JOI13_watching) C++17
100 / 100
142 ms 11896 KB
#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";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 17 ms 1664 KB Output is correct
9 Correct 19 ms 4096 KB Output is correct
10 Correct 38 ms 9344 KB Output is correct
11 Correct 33 ms 1792 KB Output is correct
12 Correct 142 ms 11896 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 3 ms 512 KB Output is correct