luogu#P11069. 「QMSOI R1」 生熏鱼

「QMSOI R1」 生熏鱼

题目背景

一切起源于一个叫神荀彧的武将...

那这道题与神荀彧的关系在哪里呢?

题目描述

一共有 nn 种攻击,第 ii 种攻击会先让你得到 aia_i 点经验,然后让你失去 bib_i 点血量。

你将依次受到 kk 次攻击,其中,第 ii 次攻击的种类是 cic_i,你的初始血量为 mm

为了获得更多的经验,你可以选择 nn 种攻击中的任意种,并防止你受到的第一次这种攻击,防止后既不会损失血量,也不会增加经验值。

现在你想知道的是在你的血量降到 00 及以下前,最多能获得多少点经验。

输入格式

一行 4 个整数,分别代表 n,m,k,sn,m,k,s,其中,ss 为随机种子,其它变量含义与题目描述相同。

因为本题输入数据过大,选手需要使用如下方式获取数据:

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

提示

样例解释

样例 11 的数据中 $a=\{953888980,904140652\},b=\{6583,80624\},c=\{1,2,1,1,2\}$。

此时显然可以不防止任何攻击或者防止第一次类型 22 的攻击获得 953888980×3+904140652=3765807592953888980\times 3+904140652=3765807592 的经验值。

可以证明,不存在获得经验值更多的方案。

数据范围

本题使用 subtask 进行捆绑测试,每个 subtask 的具体分值如下: | 子任务 | nn | kk | 分值 | | :----------: | :----------: | :----------: | :----------: | | 00 | 10\le 10 | 103\le 10^3 | 2020 | | 11 | 20\le 20 | 107\le 10^7 |3030 | | 22 | 24\le 24 | 2×107\le 2\times 10^7 |5050 |

对于所有数据,满足 1n241\le n \le 241k2×1071 \le k \le 2\times 10^71s,m1091\le s,m\le 10^9