Submission #106977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
106977	2019-04-21T11:13:43 Z	hugo_pm	Watching (JOI13_watching)	C++17	100 / 100	142 ms	11896 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 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.0 / 50.0

#	Verdict	Execution time	Memory	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

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	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