题目详情题解（0）讨论（0）提交记录（0）

AT_abc116_d.[ABC116D] Various Sushi

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

现有 NN 个寿司。每个寿司有两个参数：“寿司种类” tit_i 和 “美味程度” did_i。您现在需要在这 NN 个寿司中选择吃 KK 个。您的 “满足感” 会被按照如下标准计算：

  • 满足感是 “基础美味程度总和” 和 “多样性加成” 数值的总和。

  • “基础美味程度总和” 指的是你吃的所有寿司的美味程度的总和。

  • “多样性加成” 是 x×xx \times x，其中 xx 是你吃的寿司种类 （即一共有多少种 tt）。

您现在想要得到最大的 “满足感”。找到这个 “满足感” 的最大值。

输入格式

第一行为两个整数 NN 和 KK。

接下来从第 22 行到第 N+1N + 1 行，第 ii 行两个整数 tit_i 和 did_i，分别代表第 ii 种寿司的寿司种类和美味程度。

输出格式

输出您可以得到的 “满足感” 的最大值。

输入输出样例

  • 输入#1

    5 3
1 9
1 7
2 6
2 5
3 1

    输出#1

    26

  • 输入#2

    7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5

    输出#2

    25

  • 输入#3

    6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000

    输出#3

    4900000016

说明/提示

  • 1≤K≤N≤1051 \leq K \leq N \leq 10 ^ 5

  • 1≤ti≤N1 \leq t_i \leq N

  • 1≤di≤1091 \leq d_i \leq 10 ^ 9

  • 所有输入数据均为整数

样例解释 1

吃第 1,2,31,2,3 个寿司时，“基础美味程度总和” 为 9+7+6=229 + 7 + 6 = 22，“多样性加成” 为 2×2=42 \times 2 = 4 ，得到 “满足感” 最大值为 2626 ，可以验证不存在更好的吃法。

样例解释 2

吃第 1,2,3,41,2,3,4 个寿司，可以验证不存在更好的吃法。

样例解释 3

注意数据可能会爆 intint

输入解题思路，AI测评打分。不知道怎么写?

首页