Codeforces Round 620 (Div. 2)


A. Two Rabbits
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
0 10 2 3
0 10 3 3
900000000 1000000000 1 9999999
1 2 1 1
1 3 1 1
Output
2
-1
10
-1
1
----------------------------------------------------------------------------------------------------
B. Longest Palindrome
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
tab
one
bat
Output
6
tabbat
Input
4 2
oo
ox
xo
xx
Output
6
oxxxxo
Input
3 5
hello
codef
orces
Output
0
Input
9 4
abab
baba
abcd
bcde
cdef
defg
wxyz
zyxw
ijji
Output
20
ababwxyzijjizyxwbaba
----------------------------------------------------------------------------------------------------
C. Air Conditioner
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3 0
5 1 2
7 3 5
10 -1 0
2 12
5 7 10
10 16 20
3 -100
100 0 0
100 -50 50
200 100 100
1 100
99 -100 0
Output
YES
NO
YES
NO
----------------------------------------------------------------------------------------------------
D. Shortest and Longest LIS
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
3 <<
7 >><>><
5 >>><
Output
1 2 3
1 2 3
5 4 3 7 2 1 6
4 3 1 7 5 2 6
4 3 2 1 5
5 4 2 1 3
----------------------------------------------------------------------------------------------------
E. 1-Trees and Queries
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
1 2
2 3
3 4
4 5
5
1 3 1 2 2
1 4 1 3 2
1 4 1 3 3
4 2 3 3 9
5 2 3 3 9
Output
YES
YES
NO
YES
NO
----------------------------------------------------------------------------------------------------
F1. Animal Observation (easy version)
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4
Output
25
Input
3 3 1
1 2 3
4 5 6
7 8 9
Output
31
Input
3 3 2
1 2 3
4 5 6
7 8 9
Output
44
Input
3 3 3
1 2 3
4 5 6
7 8 9
Output
45
----------------------------------------------------------------------------------------------------
F2. Animal Observation (hard version)
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4
Output
25
Input
3 3 1
1 2 3
4 5 6
7 8 9
Output
31
Input
3 3 2
1 2 3
4 5 6
7 8 9
Output
44
Input
3 3 3
1 2 3
4 5 6
7 8 9
Output
45
----------------------------------------------------------------------------------------------------
