#1849. 环上排序信息最优分割

    ID: 1849 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1815来源:qoj.ac数据:公开样例排序

环上排序信息最优分割

环上排序信息最优分割

题目描述

标题: 环上排序信息最优分割 - 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;

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
16 584133 1584872 154106 1620031 591988 744576 1145492 27159 242511 670507 1070239 967255 904906 1001126 1473498 476319 
6 854977 1522388 1715546 755137 1587176 1693529 
10 1712058 1021608 56261 1457152 501427 1834297 1045836 1646715 1286280 1705780 
13 1970970 641553 1429549 1002213 510656 1957451 1858889 1078265 1275845 928234 400238 797898 1938240 
52 1758543 460206 560587 558575 1386552 943167 822857 1455575 1626431 1424836 599329 459246 41847 671083 1574085 1515575 1053452 343707 651053 1814315 1088382 350153 378662 1507362 181405 1135892 369991 1138284 905663 1710380 475608 1369404 1918966 261074 510207 1948737 129795 1109198 1145689 863189 1040175 1210597 1480337 896666 1884228 1082804 1669368 1693476 1701585 1484023 534475 847199
1733588007714

样例 2

5
34 1566025 85940 278880 454649 787234 1305849 154207 1474698 1600192 503961 365771 1482441 1547432 161149 264902 261751 1808604 1742906 421948 1700417 1130148 1895614 1845604 1982079 1809962 570006 806643 1147674 642303 1639211 71572 504934 1645348 777213 
12 891780 864141 142718 810549 1837977 1568362 169395 1219248 1499535 1617813 606930 1006177 
39 421146 638263 982623 1253688 733890 1502564 1621388 90815 1285797 196840 1291867 1630624 1462957 1033672 312043 1642650 157288 136780 1698395 1850134 1859805 1716992 44279 921300 756845 1513688 179844 838815 426291 1193592 1058367 847534 686174 1786395 969875 1565947 475728 260350 684753 
4 289752 684119 597468 1757604 
4 976003 1093641 457174 1953090
1998774012376