310489: CF1841F. Monocarp and a Strategic Game
Description
Monocarp plays a strategic computer game in which he develops a city. The city is inhabited by creatures of four different races — humans, elves, orcs, and dwarves.
Each inhabitant of the city has a happiness value, which is an integer. It depends on how many creatures of different races inhabit the city. Specifically, the happiness of each inhabitant is $0$ by default; it increases by $1$ for each other creature of the same race and decreases by $1$ for each creature of a hostile race. Humans are hostile to orcs (and vice versa), and elves are hostile to dwarves (and vice versa).
At the beginning of the game, Monocarp's city is not inhabited by anyone. During the game, $n$ groups of creatures will come to his city, wishing to settle there. The $i$-th group consists of $a_i$ humans, $b_i$ orcs, $c_i$ elves, and $d_i$ dwarves. Each time, Monocarp can either accept the entire group of creatures into the city, or reject the entire group.
The game calculates Monocarp's score according to the following formula: $m + k$, where $m$ is the number of inhabitants in the city, and $k$ is the sum of the happiness values of all creatures in the city.
Help Monocarp earn the maximum possible number of points by the end of the game!
InputThe first line contains an integer $n$ ($1 \leq n \leq 3 \cdot 10^{5}$) — the number of groups of creatures that come to Monocarp's city.
Then $n$ lines follow. The $i$-th of them contains four integers $a_i$, $b_i$, $c_i$, and $d_i$ ($0 \leq a_i, b_i, c_i, d_i \leq 10^{9}$) — the number of humans, orcs, elves and dwarves (respectively) in the $i$-th group.
OutputOutput a single number — the maximum score Monocarp can have by the end of the game. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-9}$. That is, if your answer is $a$, and the jury's answer is $b$, then the solution will be accepted if $\frac{|a-b|}{\max(1,|b|)} \le 10^{-9}$.
Note that the correct answer is always an integer, but sometimes it doesn't fit in $64$-bit integer types, so you are allowed to print it as a non-integer number.
ExamplesInput5 0 0 1 0 1 3 4 2 2 5 1 2 4 5 4 3 1 4 4 5Output
85Input
4 3 3 1 5 5 1 5 3 4 4 4 1 1 3 4 4Output
41Note
In the first example, the best course of action is to accept all of the groups.
In the second example, the best course of action is to accept the groups $2$ and $3$, and decline the groups $1$ and $4$.
Input
题意翻译
# Monocarp 和一款策略游戏 ## 题目描述 Monocarp 玩一个策略游戏，在游戏中他开发了一个城市。这个城市有四种不同种族的生物——人类、精灵、兽人和矮人。 城市中的每个居民都有一个幸福值，它是一个整数，取决于城市中不同种族的生物数量。具体来说，每个居民的幸福值默认为 $0$；对于同一个种族的每个其他生物，它会增加 $1$；对于每个敌对种族的每个其他生物，它会减少 $1$。人类对于兽人有敌意（反之亦然），精灵对于矮人有敌意（反之亦然）。 游戏开始时，Monocarp 的城市没有居民。在游戏中，$n$ 组生物会来到他的城市并希望在那里定居。第 $i$ 组包含 $a_{i}$ 个人类，$b_{i}$ 个兽人，$c_{i}$ 个精灵和 $d_{i}$ 个矮人。每次，Monocarp 可以接受或拒绝将整个生物群体加入城市。 游戏根据以下公式计算 Monocarp 的得分：$m+k$，其中 $m$ 是城市中的居民数量，而 $k$ 是城市中所有生物的幸福值之和。 帮助 Monocarp 通过最大化得分来获得游戏的胜利！ ## 输入格式 第一行包含整数 $n$（$1≤n≤3×10^5$）——来到 Monocarp 城市的生物组数。 接下来 $n$ 行，每行包含四个整数 $a_i$、$b_i$、$c_i$ 和 $d_i$（$0≤a_i,b_i,c_i,d_i≤10^9$），表示第 $i$ 组生物中人类、兽人、精灵和矮人的数量。 ## 输出格式 输出一个整数，表示 Monocarp 可以通过最大化得分获得的最大值。如果您的结果是 $a$，而评测机的答案是 $b$，则您的解法将被视为正确，当且仅当 $\frac{|a-b|}{\max(1,|b|)}\le10^{-9}$。 请注意，正确答案总是整数，但有时它不适合$64$位整数类型，因此您可以将其打印为非整数数字。Output
Monocarp 在一款策略电脑游戏中发展一个城市，城市将由四种种族——人类、精灵、兽人和矮人居住。每个居民的幸福感取决于城市中不同种族的居民数量。具体来说，每个居民的幸福感默认为0；对于每种族中的每一个其他成员，幸福感增加1；对于每个敌对种族的成员，幸福感减少1。人类与兽人（反之亦然）敌对，精灵与矮人（反之亦然）敌对。Monocarp 的城市初始无人居住，游戏过程中，n 组生物将来到他的城市，希望在那里定居。Monocarp 可以选择接受或拒绝整个群体。游戏的得分计算公式为：m + k，其中 m 是城市中的居民数量，k 是城市中所有生物的幸福感之和。求 Monocarp 到游戏结束时能获得的最大分数。
输入数据格式：
第一行包含一个整数 n（1 ≤ n ≤ 3 × 10^5），表示来到 Monocarp 城市的生物群体的数量。
接下来 n 行，每行包含四个整数 a_i, b_i, c_i, d_i（0 ≤ a_i, b_i, c_i, d_i ≤ 10^9），分别表示第 i 个群体中的人类、兽人、精灵和矮人的数量。
输出数据格式：
输出一个数，即 Monocarp 到游戏结束时能获得的最大分数。如果答案的绝对或相对误差不超过 10^-9，则答案被认为是正确的。正确答案总是整数，但有时不适合64位整数类型，所以允许以非整数形式打印。
示例：
输入：
5
0 0 1 0
1 3 4 2
2 5 1 2
4 5 4 3
1 4 4 5
输出：
85
输入：
4
3 3 1 5
5 1 5 3
4 4 4 1
1 3 4 4
输出：
41
注意：
在第一个示例中，最佳策略是接受所有群体。
在第二个示例中，最佳策略是接受群体2和3，拒绝群体1和4。题目大意： Monocarp 在一款策略电脑游戏中发展一个城市，城市将由四种种族——人类、精灵、兽人和矮人居住。每个居民的幸福感取决于城市中不同种族的居民数量。具体来说，每个居民的幸福感默认为0；对于每种族中的每一个其他成员，幸福感增加1；对于每个敌对种族的成员，幸福感减少1。人类与兽人（反之亦然）敌对，精灵与矮人（反之亦然）敌对。Monocarp 的城市初始无人居住，游戏过程中，n 组生物将来到他的城市，希望在那里定居。Monocarp 可以选择接受或拒绝整个群体。游戏的得分计算公式为：m + k，其中 m 是城市中的居民数量，k 是城市中所有生物的幸福感之和。求 Monocarp 到游戏结束时能获得的最大分数。 输入数据格式： 第一行包含一个整数 n（1 ≤ n ≤ 3 × 10^5），表示来到 Monocarp 城市的生物群体的数量。 接下来 n 行，每行包含四个整数 a_i, b_i, c_i, d_i（0 ≤ a_i, b_i, c_i, d_i ≤ 10^9），分别表示第 i 个群体中的人类、兽人、精灵和矮人的数量。 输出数据格式： 输出一个数，即 Monocarp 到游戏结束时能获得的最大分数。如果答案的绝对或相对误差不超过 10^-9，则答案被认为是正确的。正确答案总是整数，但有时不适合64位整数类型，所以允许以非整数形式打印。 示例： 输入： 5 0 0 1 0 1 3 4 2 2 5 1 2 4 5 4 3 1 4 4 5 输出： 85 输入： 4 3 3 1 5 5 1 5 3 4 4 4 1 1 3 4 4 输出： 41 注意： 在第一个示例中，最佳策略是接受所有群体。 在第二个示例中，最佳策略是接受群体2和3，拒绝群体1和4。