← 返回题目列表

Codeforces · 2080/B

B. 最佳跑步者

中文机器翻译题面 查看原题

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

Best Runner - 原题 PDF 第 1 页
原题PDF第4页
Best Runner - 原题 PDF 第 2 页
原题PDF第5页
可复制的 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