题目 30020

Min-Plus 卷积(凹 × 任意)

查看题解 ↗GitHub ↗如何评测
题号
30020
时间限制
10000 ms
内存限制
1024 MB
标签
数学
来源
Library Checker (yosupo06) - min_plus_convolution_concave_arbitrary

【题目描述】

给定整数序列 a0,a1,...,aN−1a_0, a_1, ..., a_{N - 1} 和 b0,b1,...,bM−1b_0, b_1, ..., b_{M - 1}。其中,aa 是凹序列。请计算按如下方式定义的整数序列 c0,c1,...,c(N−1)+(M−1)c_0, c_1, ..., c_{(N - 1) + (M - 1)}:

ck=min⁡i+j=k(ai+bj)c_k = \min_{i+j=k} (a_i+b_j)

【输入】

输入格式如下:

文本
$N$ $M$
$a_0$ $a_1$ ... $a_{N-1}$
$b_0$ $b_1$ ... $b_{M-1}$

【输出】

输出格式如下:

文本
$c_0$ $c_1$ ... $c_{(N - 1) + (M - 1)}$

【输入样例】

文本
4 5
0 2 3 1
5 1 3 3 2

【输出样例】

文本
5 1 3 3 2 4 4 3

【数据范围】

  • 1≤N,M≤5242881 \leq N, M \leq 524288
  • 0≤ai,bi≤1090 \leq a_i, b_i \leq 10^9
  • aa 是凹的,即对 0≤i<N−20 \leq i < N - 2 有 ai+1−ai≥ai+2−ai+1a_{i+1}-a_i\geq a_{i+2}-a_{i+1}。

【来源】

Library Checker(yosupo06) min_plus_convolution_concave_arbitrary

数据下载

题目 30020 的公开数据

正在读取文件列表…

常用命令

题目 30020 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。