#PQJ1815x9513. QOJ 1815_9513

    ID: 2711 传统题 4000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测排序

QOJ 1815_9513

标题: 环上排序信息最优分割 - Problem - QOJ.ac

2024-2025 集训队互测 Round 3 (Oct 20, 2024)

Statistics

给定 n 个序列 {a1,i},{a2,i},…,{an,i},第 i 个序列长度为 mi,每个序列的每个元素都是 0 到 2×106 之间的整数。定义 ai 的后继是 ai+1(1≤i≤n−1),而 an 的后继是 a1。ai 的后继记作 succ(i)。

定义一个序列的代价为,向序列中加入一个 0 和一个 2×106,排序后,相邻两个数差的平方之和。即若排序后是 0=p0≤p1≤p2≤⋯≤pk−1≤pk=2×106,那么代价为 ∑i=0k−1(pi+1−pi)2。

定义一个分割为整数序列 x1,x2,…,xn,满足 1≤xi≤mi。

定义第 i 个分割后的序列是由 ai 的 [xi,mi] 号元素,加上 asucc(i) 的 [1,xsucc(i)−1] 号元素组成的序列。定义一个分割的代价是所有 n 个分割后的序列的代价之和。

求代价最小的分割。输出最小代价的值即可。

输入格式

第一行一个整数 n。

接下来 n 行,每行包含一个整数 mi 和 mi 个整数 ai,1,…,ai,mi。

输出格式

一行一个整数表示最小代价。

样例

样例输入 1

4
5 414276 935411 204664 302847 1142143
5 162307 1199651 1168780 39659 991911
6 1204312 442315 639803 28852 1019073 143732
4 279750 1185347 612942 1086837

样例输出 1

4522800735482

数据范围与约定

记 ∑m 表示所有序列的长度之和。

对于所有数据,n≥2,mi≥2,∑m≤2×105,0≤ai,j≤2×106。

  • Subtask1(10pts):∑m≤100;
  • Subtask2(20pts):∑m≤1000;
  • Subtask3(30pts):∑m≤5×104;
  • Subtask4(40pts):∑m≤2×105;