3754 . [模板題] Min Plus Convolution (Convex and Arbitrary)

Submit out of contest
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

library-checker template

Description

Given integer sequences $a_ 0, a_ 1, ..., a_ {N - 1}$ and $b_ 0, b_ 1, ..., b_ {M - 1}$. Here, $a$ is convex. Calculate an integer sequence $c_ 0, c_ 1, ..., c_ {(N - 1) + (M - 1)}$ defined as follows:

$$c_ k = \min_ {i+j=k} (a_ i+b_ j)$$

Input Format

$N$ $M$
$a_ 0$ $a_ 1$ ... $a_ {N-1}$
$b_ 0$ $b_ 1$ ... $b_ {M-1}$

Output Format

$c_ 0$ $c_ 1$ ... $c_ {(N - 1) + (M - 1)}$

Sample Input 1

4 5
3 1 0 3
5 1 3 3 2

Sample Output 1

8 4 2 1 3 3 2 5

Hints

  • $1 \leq N, M \leq 2^ {19}$
  • $0 \leq a_ i, b_ i \leq 10^ {9}$
  • $a$ is convex. i.e. $a_ {i+1}-a_ i\leq a_ {i+2}-a_ {i+1}$ holds for $0\leq i < N - 2$.

Problem Source

library checker: min_plus_convolution_convex_arbitrary

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 2097152 2097152
1 5000 2097152 2097152
2 5000 2097152 2097152
3 5000 2097152 2097152
4 5000 2097152 2097152
5 5000 2097152 2097152
6 5000 2097152 2097152
7 5000 2097152 2097152
8 5000 2097152 2097152
9 5000 2097152 2097152
10 5000 2097152 2097152
11 5000 2097152 2097152
12 5000 2097152 2097152
13 5000 2097152 2097152
14 5000 2097152 2097152
15 5000 2097152 2097152
16 5000 2097152 2097152
17 5000 2097152 2097152
18 5000 2097152 2097152
19 5000 2097152 2097152
20 5000 2097152 2097152
21 5000 2097152 2097152
22 5000 2097152 2097152
23 5000 2097152 2097152
24 5000 2097152 2097152
25 5000 2097152 2097152
26 5000 2097152 2097152
27 5000 2097152 2097152
28 5000 2097152 2097152
29 5000 2097152 2097152
30 5000 2097152 2097152
31 5000 2097152 2097152
32 5000 2097152 2097152
33 5000 2097152 2097152
34 5000 2097152 2097152
35 5000 2097152 2097152
36 5000 2097152 2097152
37 5000 2097152 2097152
38 5000 2097152 2097152
39 5000 2097152 2097152
40 5000 2097152 2097152
Submit out of contest
Back to Top