1094: Crash的数列

内存限制:512 MB 时间限制:3.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:1 通过:1

题目描述

有一天,Crash无聊了,因此就开始做一些无聊的事,比如在一张纸上随便写了两个正整数数列。接着Crash想对这两个数列做一些操作,他想到了一种操作:分别去掉两个数列开头的几个数,也就是去掉第一个数列的前K1 (K1>0)个数和第二个数列的前K2 (K2>0)个数。假如第一个数列的前K1个数的和为S1,第二个数列的前K2个数的和为S2,则这次操作的代价为(S1-K1)×(S2-K2)。
进行多次操作后,两个数列都会变成空数列。Crash想知道使两个数列都变成空数列所需进行的操作代价和最小为多少。




输入格式

输入文件名为sequences.in,共三行。
第一行两个正整数N、M,分别表示两个数列的长度。
第二行N个正整数,表示第一个数列。
第三行M个正整数,表示第二个数列。

输出格式

输出文件名为sequences.ans,共一行,包含一个正整数,表示所需操作的最小代价和。

输入样例 复制

3 2
1 2 3
1 2

输出样例 复制

2

数据范围与提示

Crash总共进行两次操作:第一次操作去掉第一个数列的1 2和第二个数列的1,代价为0;第二次去掉第一个数列的3和第二个数列的2,代价为2。因此总代价为2。

【数据范围】
对于30%的数据满足,N,M≤70。
对于70%的数据满足,N,M≤300。
对于100%的数据满足,N,M≤2000,数列中的数≤1000。

分类标签