Processing math: 100%
编程题
                ### 问题描述

本题源自于 Codeforces:Kirill and Mushrooms

现有 n 个蘑菇,第 i 个蘑菇能量为 vi,你需要从中选择一些蘑菇制作灵药,灵药的价值为选择 蘑菇的数量 × 选择蘑菇的最小能量。

现在给你一个长度为 n 的排列 p,当你选择 k 个蘑菇,则下标为 p1,p2,...,pk1 的蘑菇能量均会变成 0

现在问你,通过选择蘑菇能得到的最大灵药价值与选择的蘑菇数量为多少?如果有多个相同的最大灵药价值答案,输出选择蘑菇数量最少的那个。

排列:对于长度为 n 的序列,其中数字 1n 均恰好出现 1 次,则我们称其为排列。

输入格式

第一行输入一个正整数 t,表示测试用例组数。(1t104)

对于每组数据:

第一行输入一个正整数 n,表示蘑菇的数量。(1n2×105)

第二行输入 n 个正整数,表示 vi(1vi109)

第三行输入 n 个正整数,表示排列 p

保证所有测试数据的 n 之和不超过 2×105

输出格式

对于每组数据:

输出一行,包含两个整数。为通过选择蘑菇能得到的最大灵药价值与选择的蘑菇数量,如果有多个相同的最大灵药价值答案,输出选择蘑菇数量最少的那个。

样例输入

6
3
9 8 14
3 2 1
5
1 2 3 4 5
1 2 3 4 5
6
1 2 3 4 5 6
6 5 4 3 2 1
5
1 4 6 10 10
2 1 4 5 3
4
2 2 5 5
4 2 3 1
5
1 2 9 10 10
1 4 2 3 5

样例输出

16 2
9 3
8 2
20 2
5 1
20 2
查看答案
赣ICP备20007335号-2