Submission #1062157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062157		beaconmc	Sprinklers (CEOI24_sprinklers)	C++14	100 / 100	184 ms	8144 KiB

Main

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;
 
ll dp[100005];
string prevs[100005];
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m;
	cin >> n >> m;
	FOR(i,0,n+1) dp[i] = -1;
 
	vector<ll> water(n);
	vector<ll> flower(m);
	FOR(i,0,n) cin >> water[i];
	FOR(i,0,m) cin >> flower[i];
 
	ll lo = 0, hi = 10000000000000000;
	while (lo < hi){
 
 
		FOR(i,0,n+1) dp[i] = -1;
		ll k = (lo+hi)/2;
		bool flag = false;
 
 
		FOR(i,0,n){
			ll sus = upper_bound(flower.begin(), flower.end(), dp[i]) - flower.begin();
 
			if (sus >= m || flower[sus] >= water[i]){
				if (water[i] + k > dp[i+1]){
					dp[i+1] = water[i] + k;
					prevs[i+1] = "R";
 
				}
 
			}else{
 
				if (abs(flower[sus] - water[i]) > k){
 
					flag = true;
				}
 
				if (i==n-1){
					if (water[i] > dp[i+1]){
						dp[i+1] = water[i];
						prevs[i+1] = "L";
					}
				}
				else{
					if (abs(flower[sus] - water[i+1]) > k){
						if (water[i] > dp[i+1]){
							dp[i+1] = water[i];
							prevs[i+1] = "L";
						}
 
					}else{
						if (water[i] > dp[i+1]){
							dp[i+1] = water[i];
							prevs[i+1] = "L";
						}
						ll maxi = max(water[i]+k, water[i+1]);
						if (maxi > dp[i+2]){
							dp[i+2] = maxi;
							prevs[i+2] = "LR";
						}
					}
				}
			}
		}
 
		if (dp[n] < flower[m-1]) flag = 1;
 
		if (flag==0) hi = k;
		else lo = k+1;
	}
	ll k = lo;
	FOR(i,0,n+1) dp[i] = -1;
 
 
	FOR(i,0,n){
 
		ll sus = upper_bound(flower.begin(), flower.end(), dp[i]) - flower.begin();
		//cout << dp[i] << " "<< sus << endl;
 
		if (sus >= m || flower[sus] >= water[i]){
 
			if (water[i] + k > dp[i+1]){
				dp[i+1] = water[i] + k;
				prevs[i+1] = "R";
 
			}
 
		}else{
 
 
 
			if (i==n-1){
				if (water[i] > dp[i+1]){
					dp[i+1] = water[i];
					prevs[i+1] = "L";
				}
			}
			else{
				if (abs(flower[sus] - water[i+1]) > k){
					
					if (water[i] > dp[i+1]){
						dp[i+1] = water[i];
						prevs[i+1] = "L";
					}
 
				}else{
					if (water[i] > dp[i+1]){
						dp[i+1] = water[i];
						prevs[i+1] = "L";
					}
					
					ll maxi = max(water[i]+k, water[i+1]);
					if (maxi > dp[i+2]){
 
						dp[i+2] = maxi;
						prevs[i+2] = "LR";
					}
				}
			}
		}
	}

 
 
 
	ll cur = n;
	string ans = "";
	while (cur != 0){
		ans += prevs[cur];
		cur -= prevs[cur].size();
	}
	reverse(ans.begin(), ans.end());
	if (lo == 10000000000000000) cout << -1;
	else{
		cout << lo << endl;
		cout << ans << endl;
	}
 
 
 
 
}

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