/ Vijos / 题库 /

旅行

旅行

时间限制:1秒  内存限制:256M


【题目描述】

  H老师旗下的 \(n\) 个OIer坐船外出旅行!

  但是他们只有一艘船,虽然船能装下全部的Oier,但太拥挤将会影响众OIer的心情,所以H老师决定选择一部分Oier去。我们假设,每个人单独坐船的快乐程度是 \(C_i\),而船上每多一个人,他的快乐程度会减去 \(D_i\)。

  现在你的任务是帮助H老师计算,选择那些人,才能使船上所有人的快乐程度之和达到最大。

【输入格式】

  第 1 行是一个整数 \(N\),表示OIer的人数;
  第 2 行有 \(N\) 个整数,第 \(i\) 个整数表示第 \(i\) 个人人单独坐船的快乐程度 \(C_i\);
  第 3 行有 \(N\) 个整数,第 \(i\) 个整数表示每多 1 人,第 \(i\) 个人快乐程度的下降值 \(D_i\)。

【输出格式】

  第 1 行一个整数,是最大的快乐程度之和;
  第 2 行一个整数,是最大的快乐程度之和所对应的汽艇上的人数(若有多种方案,则输出人数最多的)。

【输入输出样例】

 Input

6
10 10 10 10 10 9
2 2 2 2 2 3 

 Output

18
3

【数据限制】

  对于 \(30\%\) 的数据,\(1<N<20\)。
  对于 \(100\%\) 的数据,\(1<N<1000\),\(1 ≤ c_i,d_i ≤ 10000\)。

【来源】

  Mr.he

信息

ID
1759
难度
(无)
分类
搜索 | 枚举贪心 | 其他 | 排序 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
8
上传者