Submission #1043092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043092		Tob	Sprinklers (CEOI24_sprinklers)	C++14	100 / 100	115 ms	7508 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7;

int n, m;
int a[N], b[N], dp[N], gt[N];
string t[N];

void update(int x, int y, int val, string s) {
	if (dp[y] < val) {
		dp[y] = val;
		gt[y] = x;
		t[y] = s;
	}
}
void check(int k) {	
	memset(dp, -1, sizeof dp);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		if (dp[i] == -1) continue;
		if (b[dp[i]]+k >= a[i] && b[dp[i]] <= a[i]) update(i, i+1, upper_bound(b, b+m, a[i])-b, "L");
		if (b[dp[i]] >= a[i] && a[i]+k >= b[dp[i]]) update(i, i+1, upper_bound(b, b+m, a[i]+k)-b, "R");
		if (a[i]+k < b[dp[i]]) update(i, i+1, dp[i], "R");
		if (i < n-1 && b[dp[i]] < a[i] && b[dp[i]]+k >= a[i+1]) update(i, i+2, upper_bound(b, b+m, a[i]+k)-b, "LR");
	}
}

int main () {
	FIO;
	cin >> n >> m;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];
	b[m] = 2e9 + 7;
	
	if (n == 1 && a[0] > b[0] && a[n-1] < b[m-1]) {
		cout << "-1\n";
		return 0;
	}
	
	int lo = 0, hi = 1e9;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		check(mid);
		if (dp[n] == m) hi = mid;
		else lo = mid+1;
	}
	cout << lo << "\n";
	check(lo);
	
	int x = n;
	string s;
	while (x) {
		s += t[x];
		x = gt[x];
	}
	reverse(all(s));
	cout << s;

	return 0;
}

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