Submission #1140638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140638		AbdullahIshfaq	Sprinklers (CEOI24_sprinklers)	C++20	100 / 100	291 ms	4352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
const int N = 100010;
int s[N], f[N], dp[N][8], n, m;
bool check(int K){
	int ind = 0;
	for(int i = 3; i < n; i++){
		for(int mask = 0; mask < (1 << 3); mask++){
			dp[i][mask] = -1;
			for (int typ = 0; typ < 2; typ++){
				if(dp[i - 1][(mask + (typ == 1) * 8) >> 1] == -1){
                    continue;
                }
                bool ch = 1;
				for(int tmp = ind; tmp < m and f[tmp] <= s[i-1]; tmp++){
                    ll flg = 0;
					for(int k = i - 3; k <= i; k++){
						if(f[tmp] == s[k]){
                            flg = 1;
                            break;
                        }
						if((f[tmp] >= s[k]) == (((mask + (typ == 1) * 8) >> (i - k)) & 1) and abs(f[tmp] - s[k]) <= K){
                            flg = 1;
                            break ;
                        }
					}
                    if(flg){
                        continue;
                    }
                    else{
                        ch = 0;
                        break ;
                    }
				}
                if(!ch){
                    continue;
                }
				dp[i][mask] = (mask + (typ == 1) * 8) >> 1;
			}
		}
		while(ind < m and f[ind] <= s[i-1]){
			ind++;
		}
	}
	return dp[n - 1][0] != -1;
}
void solve(){
    cin >> n >> m;
	s[0] = s[1] = s[2] = -2e9;
	for(int i = 3 ;i < n + 3; i ++){
		cin >> s[i];
	}
	s[n + 3] = s[n + 4] = s[n + 5] = 2e9;
   	for(int i = 0 ;i < m; i ++){
		cin >> f[i];
	}
	n += 6;
	int l = -1, r = 1e9 + 5;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(check(mid)){
			r = mid;
		}
		else{
			l = mid;
		}
	}
	if(r == 1e9 + 5){
		cout << -1 << '\n';
	}
	else{
		check(r);
		string ans(n, 'L');
		int j = 0;
		for(int i = n - 1; i >= 0; i--){
			if(j % 2){
				ans[i] = 'R';
			}
			else{
				ans[i] = 'L';
			}
			j = dp[i][j];
		}
		cout << r << '\n';
		for(int i = 3; i < n - 3; i ++){
			cout << ans[i];
		}
		cout << '\n';
	}

	
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll tests = 1;
	// cin >> tests;
	for(ll i = 1; i <= tests; i++){
		solve();
	}
}

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