Submission #1047233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047233		alex_2008	Sprinklers (CEOI24_sprinklers)	C++14	9 / 100	66 ms	2208 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dp[N];
int from[N];
int s[N], f[N];
int n, m;
string ans_s = "";
int ind(int l, int r, int i) {
	while (i <= m && l <= f[i] && f[i] <= r) {
		i++;
	}
	i--;
	return i;
}
bool ch(int d) {
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = 0;
		int x = ind(s[i] - d, s[i], dp[i - 1] + 1);
		if (x >= dp[i]) {
			dp[i] = x;
			from[i] = 1;
		}
		x = ind(s[i], s[i] + d, dp[i - 1] + 1);
		if (x >= dp[i]) {
			dp[i] = x;
			from[i] = 2;
		}
		if (i != 1) {
			if (s[i - 1] + d <= s[i]) {
				x = ind(s[i] - d, s[i - 1] + d, dp[i - 2] + 1);
				if (x >= dp[i]) {
					dp[i] = x;
					from[i] = 3;
				}
			}
 		}
	}
	if (dp[n] < m) return false;
	ans_s.clear();
	int i = n;
	while (i != 0) {
		if (from[i] == 1) {
			ans_s.push_back('L');
			i--;
		}
		else if (from[i] == 2) {
			ans_s.push_back('R');
			i--;
		}
		else if (from[i] == 3) {
			ans_s.push_back('R');
			ans_s.push_back('L');
			i -= 2;
		}
	}
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> f[i];
	}
	int l = 0, r = 1e9 + 10, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ch(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << "\n";
	if (ans == -1) return 0;
	reverse(ans_s.begin(), ans_s.end());
	cout << ans_s << "\n";
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47