降智比赛题解
A. 气球
设 $f_i$ 表示最后一次选择的是 $i$ 的答案,暴力转移是枚举一个 $j$,判断 $c_i,c_j$ 是否相同对应乘上系数转移就行了.
我们记 $mx_i$ 表示当前考虑完的所有 $f$ 的时候 $c_k = i$ 的 $f_k$ 的最大值,那么我们转移只需要知道 $mx_{c_i}$ 和剩下的数的最大值就行了,分别记录最大值和次大值是什么即可.
int n,q,v[MAXN],c[MAXN];
LL val[MAXN],mx,cmx;
scanf("%lld%lld",&n,&q);
FOR(i,1,n) scanf("%lld",v+i);
FOR(i,1,n) scanf("%l