「SvR-2」1+2=3(加强版)

Luogu
IDLGP9153
Time1000ms
Memory128MB
DifficultyP6
欧拉回路
你有一些木棒,每个木棒左边有一个数,右边有一个数,数是 $[0,c)$ 的自然数,你要将所有木棒拼起来,使相邻的数和为 $c$ 的对数最大。 例如,$c=3$,$1\text{ - }2$ 和 $1\text{ - }0$ 两个木棒,如果按 $1\text{ - }0,1\text{ - }2$ 这样拼,相邻的数和为 $3$ 的对数是 $0$;而按 $1\text{ - }\textcolor{red}{\underline{\textbf 2}},\textcolor{red}{\underline{\textbf 1}}\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$,因为 $2+1=3$。 ## Input **本题有多组数据。** 输入的第一行一个正整数表示数据组数 $T$。 对于每组数据,第一行输入一个正整数 $c$,之后 $c$ 行,每行 $c$ 个整数,第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 为 $(i-1)\text{ - }(j-1)$ 型木棒的个数。 ## Output 共 $T$ 行,每行一个整数表示答案。 [samples] ## Note 对于 $100\%$ 的数据,$1\le T\le10^5$,$1\le a_{i,j}\le10^9$,$3\le c\le10^3$,$\sum c^2\le5\times10^6$。 **注:本题数据较弱,如有 hack 欢迎告知出题人。**
Samples
Input #1
1
3
4 1 3
4 7 7
9 10 3
Output #1
31
API Response (JSON)
{
  "problem": {
    "name": "「SvR-2」1+2=3(加强版)",
    "description": {
      "content": "你有一些木棒,每个木棒左边有一个数,右边有一个数,数是 $[0,c)$ 的自然数,你要将所有木棒拼起来,使相邻的数和为 $c$ 的对数最大。 例如,$c=3$,$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒,如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼,相邻的数和为 $3$ 的对数是 $0$;而按 $1\\text{ - }\\textcolor{",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9153"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "你有一些木棒,每个木棒左边有一个数,右边有一个数,数是 $[0,c)$ 的自然数,你要将所有木棒拼起来,使相邻的数和为 $c$ 的对数最大。\n\n例如,$c=3$,$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒,如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼,相邻的数和为 $3$ 的对数是 $0$;而按 $1\\text{ - }\\textcolor{...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments