#P7337. 『MdOI R4』Fun

    ID: 6012 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 1 Uploaded By: Tags>模拟O2优化基础算法枚举洛谷月赛

『MdOI R4』Fun

题目背景

去 NOIP 考场时有两个优良传统:打狼和喝快乐水。这两项活动都能给同学们带来快乐。

题目描述

VG 的学校有 nn 个人要去考 NOIP。

每个人有一个交通方式,第 ii 个人的交通方式为 tit_iti=1t_i=1 表示这个人坐学校大巴,ti=0t_i=0 表示这个人自己去考场。

每个人有一个颓废值,第 ii 个人的颓废值为 qiq_iqi=1q_i=1 表示这个人愿意打狼,qi=0q_i=0 表示这个人不愿意打狼。

每个人去考场时会买一瓶快乐水,但如果坐大巴且愿意打狼的人数(即满足 ti=1t_i=1qi=1q_i=1ii 个数)kk 不小于 mm,则这 kk 个人只需要买 mm 瓶快乐水。

现在,VG 统计出了所有人的交通方式和颓废值,他请你帮他求出最终所有人买快乐水的总瓶数。

输入格式

第一行三个整数 n,m,typen,m,type。其中 typetype 表示特殊限制编号,具体意义见数据范围。它可能可以帮助你获得部分分,但正解不依赖于此。

第二行 nn 个整数,第 ii 个整数为 tit_i

第三行 nn 个整数,第 ii 个整数为 qiq_i

输出格式

一行一个整数,表示所有人最终买的快乐水总瓶数。

3 1 3
1 0 1
0 1 1

3

3 1 3
1 1 1
0 1 1

2

提示

【样例解释 #1】

三个人的情况如下:

  • 11 个人乘坐大巴但不打狼;

  • 22 个人打狼但不乘坐大巴;

  • 33 个人乘坐大巴而且打狼。

所以,只有 11 个人既乘车又打狼,满足不小于 mm 的条件,故对于这 11 个人需要购买 mm 瓶快乐水,剩下 22 个人购买 22 瓶快乐水,总共须购买 33 瓶快乐水。

【数据规模与约定】

本题不采用捆绑测试

测试点编号 n,mn,m typetype tit_i qiq_i
11 30\le 30 =0=0
22 70\le 70
33 30\le 30 =1=1
44 70\le 70
55 n=mn=m =2=2 无特殊限制
66
77
88 无特殊限制 =3=3
99
1010

对于 100%100\% 的数据,1mn1001 \le m \le n \le 100ti,qi{0,1}t_i,q_i \in \{0,1\}type{0,1,2,3}type \in \{0,1,2,3\}