luogu#P11069. 「QMSOI R1」 生熏鱼
「QMSOI R1」 生熏鱼
题目背景
一切起源于一个叫神荀彧的武将...
题目描述
一共有 种攻击,第 种攻击会先让你得到 点经验,然后让你失去 点血量。
你将依次受到 次攻击,其中,第 次攻击的种类是 ,你的初始血量为 。
为了获得更多的经验,你可以选择 种攻击中的任意种,并防止你受到的第一次这种攻击,防止后既不会损失血量,也不会增加经验值。
现在你想知道的是在你的血量降到 及以下前,最多能获得多少点经验。
输入格式
一行 4 个整数,分别代表 ,其中, 为随机种子,其它变量含义与题目描述相同。
因为本题输入数据过大,选手需要使用如下方式获取数据:
const int M=1e9,C=1e5+5;
void read(){
cin>>n>>m>>k>>s;
mt19937 rand(s);
for(int i=1;i<=n;i++) a[i]=rand()%M+1,b[i]=rand()%C+1;
for(int i=1;i<=k;i++) c[i]=rand()%n+1;
}
数组含义与题目描述中相同。
输出格式
输出一行一个整数,表示你最多能获得多少点经验。
2 100000 5 114514
3765807592
提示
样例解释
样例 的数据中 $a=\{953888980,904140652\},b=\{6583,80624\},c=\{1,2,1,1,2\}$。
此时显然可以不防止任何攻击或者防止第一次类型 的攻击获得 的经验值。
可以证明,不存在获得经验值更多的方案。
数据范围
本题使用 subtask 进行捆绑测试,每个 subtask 的具体分值如下: | 子任务 | | | 分值 | | :----------: | :----------: | :----------: | :----------: | | | | | | | | | | | | | | | |
对于所有数据,满足 ,,。