打卡信奥刷题（3373）用C++实现信奥题 P9742 「KDOI-06-J」贡献系统-洪萨配资

P9742 「KDOI-06-J」贡献系统

题目描述

洛谷贡献系统上线了！

现在有nnn个人即将参加一场洛谷月赛，每个人的等级分互不相同。第iii个人的等级分是rir_iri，贡献值是cic_ici。

假设第iii个人的等级分在这nnn个人中的排名是aia_iai（排名按等级分从大到小排序），且在月赛中的排名是bib_ibi，没有两个人的排名相同。也就是说，aaa和bbb都是111到nnn的排列。比赛结束后，每个人都会执行以下操作：

若ai=bia_i=b_iai=bi，则第iii个人的等级分不会发生任何变化，因此第iii个人不会进行任何操作；
若ai>bia_i>b_iai>bi，则第iii个人的等级分会上升，因此第iii个人会给出题人点赞，导致出题人的贡献值上升cic_ici（cic_ici可能是负数，此时会导致出题人的贡献值下降）；
若ai<bia_i<b_iai<bi，则第iii个人的等级分会下降，因此第iii个人会给出题人点踩，导致出题人的贡献值下降cic_ici（cic_ici可能是负数，此时会导致出题人的贡献值上升）。

作为这场月赛唯一的出题人，初始时你的贡献值为000。你想知道，对于所有可能的排列bbb（显然，排列aaa在比赛前已经被确定），在比赛结束后你的贡献值最大是多少。

输入格式

从标准输入读入数据。

本题有多组测试数据。

输入的第一行包含一个正整数TTT，表示数据组数。

对于每组测试数据，第一行一个正整数nnn，表示参赛选手人数。

第二行包含nnn个非负整数r1,r2,…,rnr_1,r_2,\ldots,r_nr1,r2,…,rn，表示参赛选手的等级分。保证对于任意1≤i<n1\le i< n1≤i<n，ri>ri+1r_i>r_{i+1}ri>ri+1。

第三行包含nnn个整数c1,c2,…,cnc_1,c_2,\ldots,c_nc1,c2,…,cn，表示参赛选手的贡献值。

输出格式

输出到标准输出。

对于每组测试数据，输出一行一个整数，表示最大的贡献值。

输入输出样例 #1

输入 #1

3 5 3816 3738 3726 3621 3582 111 109 -50 -22 208 8 8 7 6 5 4 3 2 1 128 1 0 0 0 0 1 0 10 10 9 8 7 6 5 4 3 2 1 1 1 4 5 1 4 1 9 1 9

输出 #1

280 1 34

说明/提示

【样例解释 #1】

对于第一组测试数据，设五个人按输入顺序分别为 A，B，C，D，E，则当月赛中的排名顺序为 ABECD 时贡献值最大，为0+0−(−50)−(−22)+208=2800+0-(-50)-(-22)+208=2800+0−(−50)−(−22)+208=280。可以证明，这是唯一能使贡献值达到最大的排名顺序。

对于第二组测试数据，设八个人按输入顺序分别为 A，B，C，D，E，F，G，H，则当月赛中的排名顺序为 ABCDEGFH 时可以使贡献值达到最大值111，注意此时有多种可能的使贡献值最大的排名顺序。

【样例 #2】

见选手目录下的contrib/contrib2.in与contrib/contrib2.ans。

【样例 #3】

见选手目录下的contrib/contrib3.in与contrib/contrib3.ans。

【数据范围】

对于所有数据保证：1≤T≤51\le T\le 51≤T≤5，1≤n≤2×1051\le n\le 2\times 10^51≤n≤2×105，0≤ri≤1090\le r_i\le 10^90≤ri≤109，−109≤ci≤109-10^9\le c_i\le 10^9−109≤ci≤109，且对于任意1≤i<n1\le i<n1≤i<n，ri>ri+1r_i>r_{i+1}ri>ri+1。

测试点编号	$n\le $	特殊限制
1∼31\sim31∼3	888	无
444	100100100	ABC
555	100100100	C
6∼76\sim 76∼7	100100100	无
8∼98\sim 98∼9	5×1035\times 10^35×103	AB
10∼1110\sim 1110∼11	5×1035\times 10^35×103	C
12∼1412\sim 1412∼14	5×1035\times 10^35×103	无
151515	2×1052\times10^52×105	AB
16∼1816\sim 1816∼18	2×1052\times10^52×105	B
19∼2119\sim 2119∼21	2×1052\times10^52×105	C
22∼2522\sim 2522∼25	2×1052\times 10^52×105	无

特殊性质 A：对于任意1≤i<n1\le i<n1≤i<n，保证ci=ci+1c_i=c_{i+1}ci=ci+1；
特殊性质 B：对于任意1≤i<n1\le i<n1≤i<n，保证ci≤ci+1c_i\le c_{i+1}ci≤ci+1；
特殊性质 C：对于任意1≤i≤n1\le i\le n1≤i≤n，保证ci≥0c_i\ge 0ci≥0。

C++实现

#include<bits/stdc++.h>#definegsum(l,r)(sum[r]-sum[l-1])usingnamespacestd;typedeflonglongll;constintN=2e5+5;ll T,n,c[N],tmp,lft,rgt,sum[N],ans1,ans2;intmain(){cin>>T;while(T--){ans1=ans2=0;cin>>n;for(inti=1;i<=n;i++)scanf("%lld",&tmp);for(inti=1;i<=n;i++){scanf("%lld",c+i);sum[i]=sum[i-1]+abs(c[i]);}for(lft=1;c[lft]>0&&lft<=n;lft++);for(rgt=n;c[rgt]<0&&rgt>=1;rgt--);for(inti=1;i<lft;i++)ans1=max(ans1,-c[i]+gsum(i+1,lft-1));for(inti=n;i>rgt;i--)ans2=max(ans2,c[i]+gsum(rgt+1,i-1));cout<<ans1+ans2+gsum(lft,rgt)<<'\n';}return0;}