以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Open Olympiad in Informatics 2024/25. Second day
Moscow, March 8th, 2025
Problem Sand. Best Runner
Input file: input.txt or standard input
Output file: output.txt or standard output
Time limit: 1 second
Memory limit: 256 megabytes
There are n running tracks in the stadium with lengths a1, a2, . . ., an. There are also m runners, with
the i-th runner starting at the beginning of track bi.
All runners will train for T seconds. The training of a runner proceeds as follows:
Let the runner currently be at the beginning of track i. They will run to the end of the current track in
ai seconds. After that, they can either instantly return to the beginning of the current track, or move to
the beginning of track (i −1) (if i > 1), or to the beginning of track (i + 1) (if i < n). After this, they
continue running from the track they moved to. Once the training duration reaches T seconds, they finish
their training.
We define the best runner as the one who runs the most number of full tracks during the training time
(there may be several such runners). Determine how many tracks the best runner will run.
Input
The first line contains three integers n, m, and T (1 ≤m ≤n ≤300 000, 1 ≤T ≤109) — the number of
tracks, the number of runners, and the duration of the training.
The second line contains n integers a1, a2, . . ., an (1 ≤ai ≤109) — the lengths of the tracks.
The third line contains m integers b1, b2, . . ., bm (1 ≤b1 < b2 < . . . < bm ≤n) — the track numbers from
which the runners start.
Output
Output a single integer — the maximum number of full tracks that one of the runners can run during the
training time.
Examples
input output
5 3 10 4
4 5 2 7 1
1 2 4
4 2 11 2
4 5 7 10
2 3
Note
In the first example, the runner starting on track 4 can run the most tracks: they should run track 4, then
move to track 5 and run it 3 times.
In the second example, the runner starting on track 2 can run the second track 2 times.
Scoring
The tests for this problem consist of six groups. Points for each group are given only if all tests of the
group and all tests of the required groups are passed.
Page 4 of 11
Open Olympiad in Informatics 2024/25. Second day
Moscow, March 8th, 2025
Additional constraints Required
Group Points Comment
Groups n T ai
0 0 – – – – Examples.
1 23 n ≤1000 – – 0
2 10 – – – – ai ≤ai+1 for all 1 ≤i < n
3 16 – T ≤20 – 0
4 19 – – ai ≤20 0
5 11 – – – – m = n
6 21 – – – 0 – 5
Page 5 of 11