oj.uz

Submission #1047229

# Submission time Handle Problem Language Result Execution time Memory
1047229 2024-08-07T11:06:32 Z alex_2008 Sprinklers (CEOI24_sprinklers) C++14
9 / 100
 63 ms 3672 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int dp[N];
int from[N];
int s[N], f[N];
int n, m;
string ans_s = "";
int ind(int l, int r, int i) {
	while (i <= m && l <= f[i] && f[i] <= r) {
		i++;
	}
	i--;
	return i;
}
bool ch(int d) {
	dp[0] = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = 0;
		int x = ind(s[i] - d, s[i], dp[i - 1] + 1);
		if (x >= dp[i]) {
			dp[i] = x;
			from[i] = 1;
		}
		x = ind(s[i], s[i] + d, dp[i - 1] + 1);
		if (x >= dp[i]) {
			dp[i] = x;
			from[i] = 2;
		}
		if (i != 1) {
			if (s[i - 1] + d <= s[i]) {
				x = ind(s[i] - d, s[i - 1] + d, dp[i - 2] + 1);
				if (x >= dp[i]) {
					dp[i] = x;
					from[i] = 3;
				}
			}
 		}
	}
	if (dp[n] < m) return false;
	ans_s.clear();
	int i = n;
	while (i != 0) {
		if (from[i] == 1) {
			ans_s.push_back('L');
			i--;
		}
		else if (from[i] == 2) {
			ans_s.push_back('R');
			i--;
		}
		else if (from[i] == 3) {
			ans_s.push_back('L');
			ans_s.push_back('R');
			i -= 2;
		}
	}
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> f[i];
	}
	int l = 0, r = 1e9 + 10, ans = -1;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (ch(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << "\n";
	if (ans == -1) return 0;
	reverse(ans_s.begin(), ans_s.end());
	cout << ans_s << "\n";
}

Subtask #0
0.0 / 0.0

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct
2 Correct 17 ms 1372 KB Correct
3 Correct 0 ms 348 KB Correct
4 Correct 20 ms 1444 KB Correct
5 Correct 20 ms 1372 KB Correct
6 Correct 0 ms 348 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 4 ms 604 KB Correct
9 Correct 0 ms 348 KB Correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 21 ms 1540 KB Correct
3 Correct 5 ms 604 KB Correct
4 Correct 53 ms 3476 KB Correct
5 Correct 60 ms 3468 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 0 ms 344 KB Correct
8 Correct 47 ms 3564 KB Correct
9 Correct 47 ms 3408 KB Correct
10 Correct 52 ms 3412 KB Correct
11 Correct 31 ms 2640 KB Correct
12 Correct 37 ms 1952 KB Correct
13 Correct 41 ms 2900 KB Correct
14 Correct 51 ms 3156 KB Correct
15 Correct 49 ms 3156 KB Correct
16 Correct 36 ms 2896 KB Correct

Subtask #3
0.0 / 17.0

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

Subtask #4
0.0 / 27.0

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

Subtask #5
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Correct
2 Correct 0 ms 348 KB Correct
3 Correct 17 ms 1372 KB Correct
4 Correct 0 ms 348 KB Correct
5 Correct 20 ms 1444 KB Correct
6 Correct 20 ms 1372 KB Correct
7 Correct 0 ms 348 KB Correct
8 Correct 0 ms 348 KB Correct
9 Correct 4 ms 604 KB Correct
10 Correct 0 ms 348 KB Correct
11 Correct 21 ms 1540 KB Correct
12 Correct 5 ms 604 KB Correct
13 Correct 53 ms 3476 KB Correct
14 Correct 60 ms 3468 KB Correct
15 Correct 1 ms 344 KB Correct
16 Correct 0 ms 344 KB Correct
17 Correct 47 ms 3564 KB Correct
18 Correct 47 ms 3408 KB Correct
19 Correct 52 ms 3412 KB Correct
20 Correct 31 ms 2640 KB Correct
21 Correct 37 ms 1952 KB Correct
22 Correct 41 ms 2900 KB Correct
23 Correct 51 ms 3156 KB Correct
24 Correct 49 ms 3156 KB Correct
25 Correct 36 ms 2896 KB Correct
26 Correct 0 ms 348 KB Correct
27 Correct 0 ms 348 KB Correct
28 Incorrect 1 ms 460 KB User solution is worse than jury's solution
29 Halted 0 ms 0 KB -