oj.uz

Submission #1062139

# Submission time Handle Problem Language Result Execution time Memory
1062139 2024-08-16T19:44:19 Z beaconmc Sprinklers (CEOI24_sprinklers) C++14
3 / 100
 2000 ms 5604 KB 
#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{
						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{
					
					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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Correct
2 Correct 1 ms 3416 KB Correct

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Correct
2 Correct 7 ms 4956 KB Correct
3 Correct 1 ms 3424 KB Correct
4 Correct 8 ms 5212 KB Correct
5 Correct 8 ms 5468 KB Correct
6 Correct 1 ms 3420 KB Correct
7 Correct 1 ms 3420 KB Correct
8 Correct 2 ms 3932 KB Correct
9 Correct 1 ms 3508 KB Correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Correct
2 Execution timed out 2055 ms 5212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Correct
2 Correct 1 ms 3416 KB Correct
3 Incorrect 1 ms 3416 KB User solution is worse than jury's solution
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Correct
2 Incorrect 33 ms 5604 KB User solution is worse than jury's solution
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Correct
2 Correct 1 ms 3416 KB Correct
3 Correct 7 ms 4956 KB Correct
4 Correct 1 ms 3424 KB Correct
5 Correct 8 ms 5212 KB Correct
6 Correct 8 ms 5468 KB Correct
7 Correct 1 ms 3420 KB Correct
8 Correct 1 ms 3420 KB Correct
9 Correct 2 ms 3932 KB Correct
10 Correct 1 ms 3508 KB Correct
11 Execution timed out 2055 ms 5212 KB Time limit exceeded
12 Halted 0 ms 0 KB -