打卡信奥刷题（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的排列。比赛结束后每个人都会执行以下操作若aibia_ib_iai​bi​则第iii个人的等级分不会发生任何变化因此第iii个人不会进行任何操作若aibia_ib_iai​bi​则第iii个人的等级分会上升因此第iii个人会给出题人点赞导致出题人的贡献值上升cic_ici​cic_ici​可能是负数此时会导致出题人的贡献值下降若aibia_ib_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≤in1\le i n1≤inriri1r_ir_{i1}ri​ri1​。第三行包含nnn个整数c1,c2,…,cnc_1,c_2,\ldots,c_nc1​,c2​,…,cn​表示参赛选手的贡献值。输出格式输出到标准输出。对于每组测试数据输出一行一个整数表示最大的贡献值。输入输出样例 #1输入 #13 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输出 #1280 1 34说明/提示【样例解释 #1】对于第一组测试数据设五个人按输入顺序分别为 ABCDE则当月赛中的排名顺序为 ABECD 时贡献值最大为00−(−50)−(−22)20828000-(-50)-(-22)20828000−(−50)−(−22)208280。可以证明这是唯一能使贡献值达到最大的排名顺序。对于第二组测试数据设八个人按输入顺序分别为 ABCDEFGH则当月赛中的排名顺序为 ABCDEGFH 时可以使贡献值达到最大值111注意此时有多种可能的使贡献值最大的排名顺序。【样例 #2】见选手目录下的contrib/contrib2.in与contrib/contrib2.ans。【样例 #3】见选手目录下的contrib/contrib3.in与contrib/contrib3.ans。【数据范围】对于所有数据保证1≤T≤51\le T\le 51≤T≤51≤n≤2×1051\le n\le 2\times 10^51≤n≤2×1050≤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≤in1\le in1≤inriri1r_ir_{i1}ri​ri1​。测试点编号$n\le $特殊限制1∼31\sim31∼3888无444100100100ABC555100100100C6∼76\sim 76∼7100100100无8∼98\sim 98∼95×1035\times 10^35×103AB10∼1110\sim 1110∼115×1035\times 10^35×103C12∼1412\sim 1412∼145×1035\times 10^35×103无1515152×1052\times10^52×105AB16∼1816\sim 1816∼182×1052\times10^52×105B19∼2119\sim 2119∼212×1052\times10^52×105C22∼2522\sim 2522∼252×1052\times 10^52×105无特殊性质 A对于任意1≤in1\le in1≤in保证cici1c_ic_{i1}ci​ci1​特殊性质 B对于任意1≤in1\le in1≤in保证ci≤ci1c_i\le c_{i1}ci​≤ci1​特殊性质 C对于任意1≤i≤n1\le i\le n1≤i≤n保证ci≥0c_i\ge 0ci​≥0。C实现#includebits/stdc.h#definegsum(l,r)(sum[r]-sum[l-1])usingnamespacestd;typedeflonglongll;constintN2e55;ll T,n,c[N],tmp,lft,rgt,sum[N],ans1,ans2;intmain(){cinT;while(T--){ans1ans20;cinn;for(inti1;in;i)scanf(%lld,tmp);for(inti1;in;i){scanf(%lld,ci);sum[i]sum[i-1]abs(c[i]);}for(lft1;c[lft]0lftn;lft);for(rgtn;c[rgt]0rgt1;rgt--);for(inti1;ilft;i)ans1max(ans1,-c[i]gsum(i1,lft-1));for(intin;irgt;i--)ans2max(ans2,c[i]gsum(rgt1,i-1));coutans1ans2gsum(lft,rgt)\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容