1/23/25, 7:29 PM Problem - 2037F - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP RAYAN
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 988 (Div. 3)
F. Ardent Flames Finished
time limit per test: 4 seconds Practice
memory limit per test: 256 megabytes
You have obtained the new limited event character Xilonen. You decide to use her in combat.
There are n enemies in a line. The i 'th enemy from the left has health hi and is currently at
position xi . Xilonen has an attack damage of m , and you are ready to defeat the enemies with
→ Virtual participation
Virtual contest is a way to take part in past contest,
her. as close as possible to participation on time. It is
supported only ICPC mode for virtual contests. If
Xilonen has a powerful "ground stomp" attack. Before you perform any attacks, you select an you've seen these problems, a virtual contest is not
for you - solve these problems in the archive. If you
integer p and position Xilonen there (p can be any integer position, including a position with an just want to solve some problem from a contest, a
virtual contest is not for you - solve this problem in
enemy currently). Afterwards, for each attack, she deals m damage to an enemy at position p (if the archive. Never use someone else's code, read
there are any), m − 1 damage to enemies at positions p − 1 and p + 1 , m − 2 damage to the tutorials or communicate with other person
during a virtual contest.
enemies at positions p − 2 and p + 2 , and so on. Enemies that are at least a distance of m
away from Xilonen take no damage from attacks. Start virtual contest
Formally, if there is an enemy at position x , she will deal max(0, m − |p − x|) damage to that
enemy each hit. Note that you may not choose a different p for different attacks. → Clone Contest to Mashup
Over all possible p , output the minimum number of attacks Xilonen must perform to defeat at
least k enemies. If it is impossible to find a p such that eventually at least k enemies will be → Submit?
defeated, output −1 instead. Note that an enemy is considered to be defeated if its health
reaches 0 or below. Language: GNU G++20 13.2 (64 bit, winlibs)
Input Choose
Choose File No file chosen
4 file:
The first line contains an integer t (1 ≤ t ≤ 10 ) – the number of test cases.
Submit
The first line of each test case contains three integers n , m , and k (1 ≤ k ≤ n ≤ 10
5
,
9
1 ≤ m ≤ 10 ).
The following line contains n integers h1 , h2 , . . . , hn (1 ≤ hi ≤ 10
9
). → Contest materials
The last line of each testcase contains n integers x1 , x2 , . . . , xn (1 ≤ x i ≤ 10
9
, xi < x i+1 Announcement (en)
for all 1 ≤ i < n) Video Tutorial (en)
It is guaranteed that the sum of n over all test cases does not exceed 10 .
5 Tutorial #2 (en)
Output
For each test case, output an integer on a new line, the minimum number of attacks that must be
performed to defeat at least k enemies. If it is impossible to find a p such that eventually at least
k enemies will be defeated, output −1 instead.
Example
input Copy
6
5 5 3
7 7 7 7 7
1 2 3 4 5
9 5 9
2 4 6 8 10 8 6 4 2
1 2 3 4 5 6 7 8 9
2 10 2
1 1
1 20
2 10 1
69696969 420420420
1 20
2 10 2
10 15
1 19
2 2 2
1000000000 1
1 3
output Copy
[Link] 1/2
1/23/25, 7:29 PM Problem - 2037F - Codeforces
2
2
-1
6969697
15
1000000000
Note
In the first testcase, it is optimal to select p = 2 . Each attack, the first enemy takes
5 − |2 − 1| = 4 damage, the second enemy takes 5 damage, the third enemy takes 4
damage, the fourth enemy takes 3 damage, and the fifth enemy takes 2 damage. After 2 attacks,
the first three enemies will be defeated. It can be shown that it is impossible to defeat 3 enemies
in less than 2 attacks, no matter which p is selected.
In the second testcase, we must kill all 9 enemies. By selecting p = 5 , all nine enemies will be
defeated in 2 attacks.
In the third testcase, we must kill both enemies. However, it can be shown that no p selected will
damage both enemies at the same time, so the answer is −1.
In the fourth testcase, selecting p = 1 will enable us to defeat the first enemy in 6969697
attacks.
In the fifth testcase, selecting p = 10 will make each enemy take 1 damage per attack. Both
enemies will be defeated in 15 attacks.
Codeforces (c) Copyright 2010-2025 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jan/23/2025 11:34:14UTC+5 (i2).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
[Link] 2/2