1963: [USACO 2022 US Open Contest Silver] Problem 1. Visits
文件提交：无需freopen
内存限制：256 MB
时间限制：2.000 S
评测方式：普通裁判
命题人：
提交：1
解决：1
题目描述
Each of Bessie’s N () bovine buddies (conveniently labeled ) owns her own farm. For each , buddy wants to visit buddy ().
Given a permutation of , the visits occur as follows.
For each from 1 up to :
- If buddy has already departed her farm, then buddy remains at her own farm.
- Otherwise, buddy departs her farm to visit buddy ’s farm. This visit results in a joyful "moo" being uttered times (0).
Compute the maximum possible number of moos after all visits, over all possible permutations .
输入
The first line contains N.
For each 1≤i≤N, the i+1-st line contains two space-separated integers ai and vi.
输出
A single integer denoting the answer.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
样例输入
4
2 10
3 20
4 30
1 40样例输出
90提示
If then
- Buddy visits buddy 's farm, resulting in moos.
- Buddy 4 sees that buddy 1 has already departed, so nothing happens.
- Buddy 3 visits buddy 4's farm, adding 30 moos.
- Buddy 2 sees that buddy 3 has already departed, so nothing happens.
This gives a total of moos.
On the other hand, if then
- Buddy 2 visits buddy 's farm, causing 20 moos.
- Buddy visits buddy 's farm, causing 30
- Buddy 4 visits buddy 1's farm, causing moos.
- Buddy sees that buddy 2 has already departed, so nothing happens.
This gives total moos. It can be shown that this is the maximum possible amount after all visits, over all permutations p.
Scoring: