回复 @顺其自然 :
为何一直关注我？

居然把m打成了n

回复 @派大大 :
Firenze已逝、、

终于完成了C++的伟大复兴、、

回复 @cstdio :
友元可好？

回复 @O(∩_∩)O :
我也跑了快两秒…………

贪心

回复 @猹比 :
祸雷锋OTZZZZZZZZZZZZZZZZ

只是想打个暴力看看能拿多少分，结果竟然AAAAAAAAAA，而且我是按60%数据范围写的代码，都没有运行错误。
我能说神魔。

AC100了。

按$L_i * R_i$排序，贪心选择。
证明：
$设最优解为\{1,2,...n\}上的一个排列\{p_i\}, \\ 设T_i = \prod_{0<j<i} L_{p_i}.第i个大臣的奖励为A_i. $
$ \forall i \in \{1,2,...n-1\},考虑相邻两大臣p_i 和 p_{i+1},\\ 设将两人交换位置后第i个大臣的奖励为{A'}_i$
则有$ \\ A_i = (T_{i-1}) / (R_{p_i}) \\
A_{i+1} = ((T_{i-1}) * (L_{p_i}) / (R_{p_{i+1}}); \\
{A'}_i = (T_{i-1}) / (R_{p_{i+1}}); \\
{A'}_{i+1} = (T_{i-1}) * (L_{p_{i+1}}) / (R_{p_i}); $
故$ A_i ≤ A'_{i+1};\,\,\,\,\,\,\, A'_i ≤ A_{i+1}; $
$ \forall i \in \{1,2,...n-1\}, \\ L_i * R_i ≤ L_{i+1} * R_{i+1} \\ \rightarrow (L_{p_i} / R_{p_{i+1}}) ≤ (L_{p_{i+1}} / R_{p_i}) \\
\rightarrow A_{i+1} ≤ A'_{i+1} \\ \rightarrow max(A_i, A_{i+1}) ≤ A'_{i+1} \\
故交换p_i, p_{i+1}得到的排列一定不比{p_i}更优$

回复 @真呆菌dsb :
我也来

路在最开始都是好的，注意是湖，就是说是个环，两点之间有两条路径

曹操曹操，论m和n的区别、、

与机器分配略有不同。。

没有注销输出的交了好几次、、尼玛调了半天

dijstra无压力秒杀.

O（n*n）效率竟然过了，评测机还真是给力。

回复 @派大大 :
大神贪心算法狂拽炫酷D炸天