广州集训今天比赛的第十题,AK哥做出来了@假伪人
T116587.奶茶搭配
普及/提高-
加入题单
通过率:
53.33%
时间限制:
1.00s
内存限制:
128MB
题目描述
小码奶茶店新开业!有 N 种茶底和 M 种小料。
一杯奶茶 = 1 种茶底 + 1 种小料,价格就是茶底价加小料价。
但小码王搞了个封顶价 P 元——如果茶底加小料的价格超过 P 元,就只收 P 元!
小码君帮忙算算:所有 N×M 种搭配,一共能卖出多少钱?
输入格式
第一行三个整数 N,M,P,分别表示茶底种类数、小料种类数和封顶价格。(1≤N,M≤2×10
5
,1≤P≤2×10
8
)
第二行 N 个整数 A
i
,表示每种茶底的价格。(1≤A
i
≤10
8
)
第三行 M 个整数 B
j
,表示每种小料的价格。(1≤B
j
≤10
8
)
输出格式
输出一个整数,表示所有奶茶搭配的总收入。答案在 64 位有符号整数范围内。
输入输出样例
输入#1
2 2 6
2 4
3 5
输出#1
23
输入#2
2 2 100
1 2
3 4
输出#2
20
输入#3
2 2 5
4 5
6 7
输出#3
20
输入#4
7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857
输出#4
2115597124
说明/提示
【样例 1 解释】
茶底 [2,4],小料 [3,5],封顶价 6 元。有部分搭配超过封顶价:
茶底 小料 原价 实付
2 3 5 5
2 5 7 6(封顶)
4 3 7 6(封顶)
4 5 9 6(封顶)
总收入 =5+6+6+6=23 元。
【样例 2 解释】
茶底 [1,2],小料 [3,4],封顶价 100 元。所有原价都不超过 100,没有触发封顶:
茶底 小料 原价 实付
1 3 4 4
1 4 5 5
2 3 5 5
2 4 6 6
总收入 =4+5+5+6=20 元。
【样例 3 解释】
茶底 [4,5],小料 [6,7],封顶价 5 元。所有原价都超过 5,全部按封顶价 5 元收:
茶底 小料 原价 实付
4 6 10 5(封顶)
4 7 11 5(封顶)
5 6 11 5(封顶)
5 7 12 5(封顶)
总收入 =5×4=20 元。
【样例 4 解释】
7 种茶底、12 种小料,封顶价 25514963 元。共有 7×12=84 种搭配,部分原价超过封顶价,部分没有。把每种搭配的实付加起来,总收入为 2115597124 元。
AK哥太强了,学习一下。