#E. 供水系统

    传统题 1000ms 256MiB

供水系统

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本道题目为本场比赛的 Bonus 题目,整体思维、难度、技巧以及知识面上与 S 组略有不同,欢迎各位强者来挑战~

题目描述

现有一个供水系统,由 nnmm 列共 nmnm 个调配单元组成。顾名思义,调配单元可以收集到达该单元的水并控制从每个水管输出的水量。

iijj 列的调配单元记作 fi,jf_{i,j},则 fi,jf_{i,j} 可以直接通过水管到达 fi+1,jf_{i+1,j}fi,j+1f_{i,j+1}水管是单向的。

调配单元相当精密,fi,jf_{i,j} 在调配 ai+bja_i+b_j 吨水后会迅速报废,经过这个单元的水会全部喷到旁边的草地里,其中数列 a,ba,b 是给定的参数。

由于该系统十分重要,小I想问你,最多有多少从左上角(f1,1f_{1,1})进入调配系统的水能进入右下角(fn,mf_{n,m})?

输入格式

第一行,两个整数 n,mn,m 表示供水系统的行数和列数。

第二行,nn 个整数 a1na_{1\ldots n},含义同描述。

第三行,mm 个整数 a1ma_{1\ldots m},含义同描述。

输出格式

一行一个整数,表示最大通过量。单位为吨。

样例 #1

样例输入 #1

4 3
19 2 3 10
20 1 50

样例输出 #1

38

提示

【样例解释】 image.png 第一行是 f1,xf_{1,x},第一列是 fx,1f_{x,1},其余类推,圆圈内是该单元的调配最大吨数,红色是管道,旁边数字表示经过水量。

子任务编号 nn\leq mm\leq 其他性质 分值
1 11 2
2 aia_i 全相等,bib_i 全相等
3 22 3
4 33
5 2525 30
6 aia_i 全相等 15
7 45

对于所有数据,n105,m105;ai,bi109n\le 10^5,m\le 10^5;a_i,b_i\le 10^9

[YDRG#003 Div. 1] YDSP-S 组赛前模拟 · 云斗杯十月 Golden Round

已参加
状态
已结束 (已参加)
规则
OI
题目
6
开始于
2023-10-14 8:30
结束于
2023-10-14 13:30
持续时间
5 小时
主持人
参赛人数
287