AT_agc076_e.[AGC076E] Squared Norm Maximization

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

给定 $N$ 对整数 $(A_1, B_1), (A_2, B_2), \cdots, (A_N, B_N)$ 。

对于 $\{1,2,\cdots,N\}$ 的任意子集 $s$ ，我们定义它的得分为：

$ (\sum_{i \in s} A_i)^2 + (\sum_{i \in s} B_i)^2 - 3 \sum_{i \in s} (A_i^2 + B_i^2) $

请你求出得分的最大可能值。

本题包含 $T$ 组测试数据。

输入格式

输入从标准输入读入，格式如下：

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

其中每组测试数据格式如下：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$

输出格式

输出共 $T$ 行，第 $i$ 行输出第 $i$ 组数据的答案。

输入输出样例

输入#1

4
4
1 0
0 1
-1 0
0 -1
4
1 0
1 0
1 0
1 0
6
1 -9
-7 -2
0 -10
10 1
2 -8
1 -8
10
19271058 -140039457
-3441379 -134156148
227767903 -70474702
-837477 -74699717
153584327 80404336
115741008 -22141349
-190028077 -21940357
76149725 17176032
159846847 -296045185
-53332199 142922717

输出#1

0
4
296
178262497119089558

说明/提示

样例解释 1

对于第一个测试点，当 $s=\{\}$ 时，得分为 $0$ ，为最大值。

对于第二个测试点， $s=\{1,2,3,4\}$ 时得分为 $4$ ，为最大值。

数据范围

$1 \leq T \leq 250000$
$1 \leq N \leq 250000$
$\sum_{1 \leq i \leq N} |A_i| \leq 10^9$
$\sum_{1 \leq i \leq N} |B_i| \leq 10^9$
所有测试点中 $N$ 的总和不超过 $250000$ 。
所有输入值均为整数。

由 ChatGPT 5 翻译

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

首页