답안 #106976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
106976	2019-04-21T11:10:31 Z	hugo_pm	구경하기 (JOI13_watching)	C++17	50 / 100	1000 ms	11904 KB

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.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 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	3 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	3 ms	384 KB	Output is correct
11	Correct	4 ms	612 KB	Output is correct
12	Correct	4 ms	512 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct

Subtask #2

0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	3 ms	432 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	206 ms	1664 KB	Output is correct
9	Correct	149 ms	4096 KB	Output is correct
10	Correct	215 ms	9420 KB	Output is correct
11	Correct	267 ms	1904 KB	Output is correct
12	Execution timed out	1071 ms	11904 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-