TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3484
  • 問題
  • P3484旅行
    制限 : 時間制限 : 30000 MS   メモリ制限 : 165536 KB
    問題説明

    Mr_H 旗下的 n 个OIer 坐船外出旅行!
    但是他们只有一艘船,虽然船能装下全部的Oier,但太拥挤将会影响众OIer 的心情,所以Mr_H决定选择一部分Oier 去。我们假设,每个人单独坐船的快乐程度是Ci,而船上每多一个人,他的快乐程度会减去Di。
    现在你的任务是帮助Mr_H 计算,选择那些人,才能使船上所有人的快乐程度之和达到最大。

    入力形式

    第 1 行是一个整数n,表示OIer 的人数;
    第 2 行有n 个整数,第i 个整数表示第i 个人人单独坐船的快乐程度Ci(1<=Ci<=10000);
    第 3 行有n 个整数,第i 个整数表示每多1 人,第i 个人快乐程度的下降值Di(1<=Di<=10)。

    出力形式

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

    サンプル入力

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

    サンプル出力

    18
    3

    ヒント

    【样例解释】
    前 3 个人去坐汽艇可使快乐程度之和达到最大,每个人的快乐程度均为10-2*2=6,总和是18。
    【数据范围】
    对于 30%的数据,n<=20;
    对于100%的数据,n<=1000。


    ソース  by YZ