Submission #633969

#	Time	Username	Problem	Language	Result	Execution time	Memory
633969		MarcosPauloEvers	Watching (JOI13_watching)	C++17	100 / 100	441 ms	31856 KiB

watching

#include <bits/stdc++.h>
#define int long long

#define CALC(X, w) \
	for (int i = 1; i <= n; i++) \
		for (X[i] = X[i - 1]; \
			 X[i] + 1 < i && pos[i] - pos[X[i] + 1] + 1 > (w); \
			 X[i]++);

using namespace std;

const int MAXN  = 2010;
int n, p, q;
int pos[MAXN];
int f[MAXN], g[MAXN];
int opt[MAXN][MAXN];

signed
main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++)
		cin >> pos[i];

	sort(pos + 1, pos + 1 + n);

	int l = 1, r = 1000000000;
	while (l <= r) {
		int w = (l + r) >> 1;

		f[0] = g[0] = 0;
		opt[0][0] = 0;

		CALC(f, w);
		CALC(g, 2*w);

		for (int i = 1; i <= min(n, p); i++)
			for (opt[i][0] = opt[i - 1][0];
				 opt[i][0] < n && (f[opt[i][0] + 1] <= opt[i - 1][0]);
				 opt[i][0]++);

		for (int i = 1; i <= min(n, q); i++)
			for (opt[0][i] = opt[0][i - 1];
				 opt[0][i] < n && (g[opt[0][i] + 1] <= opt[0][i - 1]);
				 opt[0][i]++);

		for (int i = 1; i <= min(n, p); i++)
			for (int j = 1; j <= min(n, q); j++)
				for (opt[i][j] = max(opt[i][j - 1], opt[i - 1][j]);
					 opt[i][j] < n && (f[opt[i][j] + 1] <= opt[i - 1][j] || g[opt[i][j] + 1] <= opt[i][j - 1]);
					 opt[i][j]++);

		if (opt[min(n, p)][min(n, q)] < n) l = w + 1;
		else r = w - 1;
	}
	cout << l << "\n";
	return 0;
}

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