COCI '22 Contest 4 #2 Zrinka

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You are given two arrays of length n and m respectively, which consist only of 0's and 1's.

Your task is to replace every zero with an even positive integer and every one with an odd positive integer. After replacements, both arrays should be increasing and you can use each positive integer at most once.

As this would be too easy, you are asked to do it such that the largest number you use is as small as possible.

Given two arrays, output the minimum possible largest number that needs to be used.

Input Specification

The first array is of length n (0 \le n \le 5\,000), the second is of length m (1 \le m \le 5\,000).

The first line consists of n+1 integers, the first being n, and the others describing the first array.

The second line consists of m+1 integers, the first being m, and the others describing the second array.

Output Specification

The first and only line should contain a positive integer, the answer to the question above.

Constraints

Subtask Points Constraints
1 15 n = 0
2 20 The first array consists only of 0's.
3 15 n, m \le 500
4 20 No additional constraints.

Sample Input 1

0
4 1 0 1 1

Sample Output 1

5

Sample Input 2

4 0 1 0 1
4 1 0 0 1

Sample Output 2

9

Explanation for Sample 2

One of the possible solutions is (2, 3, 4, 5) and (1, 6, 8, 9).

Sample Input 3

5 0 1 0 0 1
4 0 0 0 1

Sample Output 3

13

Explanation for Sample 3

One of the possible solutions is (2, 3, 6, 8, 9) and (4, 10, 12, 13).


Comments

There are no comments at the moment.