Submission #1041127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041127		Lucpp	Sprinklers (CEOI24_sprinklers)	C++17	3 / 100	447 ms	8580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)size(x)

constexpr ll inf = 1e9 + 10;

int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<ll> s(n), f(m);
	for(ll& e : s) cin >> e;
	for(ll& e : f) cin >> e;
	auto check = [&](ll len) -> string {
		vector<int> dp(n+1);
		vector<pair<int, string>> prv(n+1);
		for(int i = 0; i < n; i++){
			ll nxtf = dp[i] < m ? f[dp[i]] : inf;
			if(nxtf + len < s[i]) continue;
			vector<tuple<int, int, string>> opts;
			opts.emplace_back(i+1, upper_bound(all(f), s[i]) - f.begin(), "L");
			if(nxtf >= s[i]) opts.emplace_back(i+1, upper_bound(all(f), s[i]+len) - f.begin(), "R");
			if(i < n-1 && s[i+1]-len <= nxtf) opts.emplace_back(i+2, upper_bound(all(f), s[i]+len) - f.begin(), "RL");
			for(auto [i2, x, str] : opts){
				if(dp[i2] < x){
					dp[i2] = x;
					prv[i2] = {i, str};
				}
			}
		}
		if(dp[n] < m) return "";
		int i = n;
		string rec;
		while(i > 0){
			auto [i2, str] = prv[i];
			reverse(all(str));
			rec += str;
			i = i2;
		}
		reverse(all(rec));
		return rec;
	};
	ll lo = -1, hi = inf;
	while(lo+1 < hi){
		ll mid = (lo + hi) / 2;
		if(check(mid) == "") lo = mid;
		else hi = mid;
	}
	if(hi == inf) cout << "-1\n";
	else{
		cout << hi << "\n";
		cout << check(hi) << "\n";
	}
}

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