FPEvalDataset/LeetCodeProblem
0302
1{2 "id": 2633,3 "name": "minimum_cost_to_split_an_array",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/minimum-cost-to-split-an-array/",6 "date": "2023-01-15 00:00:00",7 "task_description": "You are given an integer array `nums` and an integer `k`. Split the array into some number of non-empty subarrays. The **cost** of a split is the sum of the **importance value** of each subarray in the split. Let `trimmed(subarray)` be the version of the subarray where all numbers which appear only once are removed. For example, `trimmed([3,1,2,4,3,4]) = [3,4,3,4].` The **importance value** of a subarray is `k + trimmed(subarray).length`. For example, if a subarray is `[1,2,3,3,3,4,4]`, then trimmed(`[1,2,3,3,3,4,4]) = [3,3,3,4,4].`The importance value of this subarray will be `k + 5`. Return _the minimum possible cost of a split of _`nums`. A **subarray** is a contiguous **non-empty** sequence of elements within an array. **Example 1:** ``` **Input:** nums = [1,2,1,2,1,3,3], k = 2 **Output:** 8 **Explanation:** We split nums to have two subarrays: [1,2], [1,2,1,3,3]. The importance value of [1,2] is 2 + (0) = 2. The importance value of [1,2,1,3,3] is 2 + (2 + 2) = 6. The cost of the split is 2 + 6 = 8. It can be shown that this is the minimum possible cost among all the possible splits. ``` **Example 2:** ``` **Input:** nums = [1,2,1,2,1], k = 2 **Output:** 6 **Explanation:** We split nums to have two subarrays: [1,2], [1,2,1]. The importance value of [1,2] is 2 + (0) = 2. The importance value of [1,2,1] is 2 + (2) = 4. The cost of the split is 2 + 4 = 6. It can be shown that this is the minimum possible cost among all the possible splits. ``` **Example 3:** ``` **Input:** nums = [1,2,1,2,1], k = 5 **Output:** 10 **Explanation:** We split nums to have one subarray: [1,2,1,2,1]. The importance value of [1,2,1,2,1] is 5 + (3 + 2) = 10. The cost of the split is 10. It can be shown that this is the minimum possible cost among all the possible splits. ``` **Constraints:** `1 <= nums.length <= 1000` `0 <= nums[i] < nums.length` `1 <= k <= 109`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,2,1,2,1,3,3], k = 2",12 "output": "8 "13 },14 {15 "label": "Example 2",16 "input": "nums = [1,2,1,2,1], k = 2",17 "output": "6 "18 },19 {20 "label": "Example 3",21 "input": "nums = [1,2,1,2,1], k = 5",22 "output": "10 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 556,30 295,31 236,32 505,33 105,34 289,35 147,36 189,37 148,38 495,39 184,40 477,41 405,42 14,43 117,44 380,45 585,46 124,47 22,48 152,49 105,50 115,51 407,52 366,53 143,54 525,55 274,56 11,57 340,58 133,59 298,60 565,61 577,62 398,63 283,64 117,65 163,66 593,67 535,68 259,69 177,70 211,71 340,72 436,73 130,74 112,75 148,76 65,77 342,78 580,79 361,80 430,81 581,82 285,83 378,84 425,85 218,86 214,87 592,88 491,89 342,90 363,91 94,92 394,93 555,94 232,95 308,96 345,97 95,98 600,99 412,100 131,101 115,102 390,103 170,104 75,105 556,106 501,107 391,108 7,109 99,110 242,111 576,112 556,113 369,114 126,115 55,116 491,117 386,118 168,119 587,120 582,121 316,122 199,123 171,124 122,125 591,126 184,127 299,128 570,129 596,130 42,131 545,132 191,133 239,134 474,135 115,136 301,137 571,138 4,139 214,140 257,141 125,142 161,143 596,144 330,145 174,146 243,147 360,148 608,149 388,150 358,151 300,152 521,153 610,154 134,155 385,156 56,157 146,158 394,159 29,160 422,161 285,162 79,163 156,164 294,165 269,166 35,167 371,168 143,169 610,170 293,171 403,172 139,173 381,174 53,175 35,176 4,177 498,178 590,179 451,180 101,181 560,182 525,183 11,184 411,185 524,186 371,187 352,188 196,189 170,190 214,191 236,192 232,193 340,194 568,195 283,196 600,197 31,198 114,199 115,200 500,201 178,202 72,203 372,204 344,205 98,206 160,207 36,208 475,209 151,210 132,211 560,212 432,213 23,214 21,215 130,216 429,217 109,218 176,219 582,220 472,221 492,222 166,223 595,224 163,225 62,226 274,227 223,228 430,229 532,230 519,231 239,232 402,233 494,234 176,235 197,236 85,237 278,238 330,239 502,240 157,241 101,242 47,243 122,244 219,245 313,246 252,247 432,248 412,249 493,250 289,251 535,252 427,253 244,254 498,255 561,256 377,257 296,258 167,259 502,260 497,261 519,262 580,263 339,264 418,265 379,266 232,267 41,268 553,269 133,270 28,271 242,272 151,273 445,274 319,275 526,276 326,277 403,278 487,279 449,280 448,281 361,282 297,283 110,284 1,285 129,286 293,287 20,288 23,289 389,290 92,291 37,292 66,293 222,294 403,295 155,296 180,297 251,298 258,299 530,300 386,301 271,302 414,303 477,304 4,305 509,306 575,307 56,308 335,309 604,310 546,311 426,312 88,313 412,314 75,315 245,316 445,317 448,318 161,319 535,320 53,321 171,322 197,323 456,324 292,325 611,326 337,327 321,328 473,329 294,330 12,331 113,332 528,333 52,334 424,335 24,336 201,337 428,338 378,339 71,340 551,341 486,342 458,343 279,344 567,345 41,346 312,347 374,348 28,349 426,350 567,351 280,352 447,353 552,354 432,355 516,356 479,357 369,358 276,359 465,360 287,361 101,362 521,363 177,364 164,365 162,366 298,367 472,368 399,369 104,370 545,371 562,372 342,373 278,374 371,375 115,376 245,377 258,378 154,379 248,380 46,381 257,382 18,383 360,384 322,385 302,386 31,387 593,388 425,389 107,390 405,391 290,392 264,393 365,394 548,395 400,396 200,397 132,398 312,399 257,400 524,401 534,402 31,403 545,404 554,405 601,406 211,407 472,408 402,409 493,410 28,411 583,412 367,413 16,414 282,415 565,416 488,417 351,418 517,419 503,420 148,421 389,422 78,423 14,424 208,425 482,426 153,427 80,428 336,429 570,430 537,431 1,432 226,433 387,434 150,435 394,436 275,437 17,438 387,439 577,440 454,441 293,442 356,443 548,444 464,445 197,446 291,447 47,448 299,449 62,450 197,451 278,452 286,453 188,454 486,455 601,456 15,457 594,458 276,459 160,460 265,461 159,462 188,463 119,464 259,465 116,466 5,467 521,468 58,469 146,470 222,471 610,472 141,473 419,474 514,475 324,476 352,477 188,478 244,479 80,480 572,481 292,482 293,483 62,484 357,485 293,486 376,487 100,488 450,489 156,490 440,491 84,492 305,493 239,494 424,495 419,496 406,497 254,498 213,499 558,500 100,501 553,502 1,503 113,504 153,505 97,506 189,507 101,508 302,509 217,510 414,511 407,512 515,513 31,514 194,515 158,516 237,517 418,518 592,519 387,520 345,521 182,522 439,523 505,524 59,525 91,526 220,527 428,528 178,529 94,530 606,531 122,532 412,533 443,534 471,535 363,536 331,537 176,538 324,539 502,540 123,541 244,542 261,543 385,544 310,545 455,546 609,547 213,548 557,549 443,550 347,551 428,552 123,553 157,554 561,555 286,556 317,557 136,558 324,559 565,560 87,561 395,562 598,563 529,564 451,565 10,566 574,567 540,568 351,569 305,570 560,571 427,572 503,573 575,574 71,575 70,576 431,577 114,578 147,579 0,580 577,581 496,582 227,583 447,584 441,585 350,586 47,587 500,588 610,589 539,590 209,591 514,592 490,593 320,594 539,595 515,596 567,597 308,598 327,599 74,600 494,601 579,602 551,603 420,604 494,605 35,606 603,607 9,608 473,609 31,610 105,611 353,612 116,613 503,614 403,615 163,616 151,617 195,618 146,619 544,620 338,621 537,622 188,623 132,624 375,625 300,626 571,627 396,628 398,629 201,630 356,631 603,632 291,633 228,634 566,635 53,636 236,637 583,638 209,639 241,640 288641 ],642 318885581643 ],644 "output": 318885978645 },646 {647 "input": [648 [649 436,650 88,651 79,652 214,653 18,654 319,655 225,656 299,657 468,658 11,659 446,660 320,661 111,662 295,663 115,664 449,665 195,666 57,667 75,668 493,669 460,670 229,671 460,672 75,673 215,674 208,675 372,676 255,677 398,678 484,679 400,680 265,681 102,682 24,683 79,684 384,685 363,686 58,687 220,688 256,689 323,690 141,691 177,692 80,693 321,694 471,695 20,696 219,697 263,698 353,699 135,700 127,701 478,702 143,703 197,704 431,705 241,706 461,707 475,708 36,709 146,710 51,711 452,712 336,713 370,714 217,715 97,716 92,717 443,718 343,719 379,720 378,721 375,722 251,723 31,724 246,725 159,726 259,727 519,728 33,729 212,730 199,731 415,732 230,733 404,734 350,735 98,736 37,737 287,738 158,739 234,740 7,741 281,742 365,743 507,744 380,745 363,746 230,747 170,748 159,749 492,750 232,751 122,752 98,753 380,754 196,755 520,756 480,757 218,758 490,759 120,760 453,761 177,762 134,763 457,764 199,765 361,766 54,767 241,768 416,769 107,770 339,771 425,772 249,773 246,774 39,775 529,776 48,777 42,778 342,779 136,780 128,781 311,782 460,783 189,784 150,785 272,786 211,787 404,788 358,789 462,790 496,791 327,792 102,793 428,794 507,795 468,796 170,797 273,798 54,799 52,800 444,801 34,802 292,803 479,804 262,805 15,806 436,807 480,808 226,809 175,810 216,811 71,812 501,813 361,814 155,815 139,816 200,817 148,818 422,819 93,820 383,821 195,822 88,823 29,824 251,825 336,826 100,827 456,828 291,829 367,830 50,831 364,832 409,833 158,834 372,835 223,836 470,837 289,838 471,839 451,840 359,841 345,842 435,843 16,844 360,845 234,846 402,847 105,848 5,849 351,850 310,851 51,852 39,853 288,854 73,855 379,856 306,857 331,858 80,859 275,860 217,861 125,862 423,863 75,864 334,865 61,866 108,867 165,868 11,869 112,870 486,871 62,872 85,873 105,874 268,875 255,876 76,877 406,878 382,879 317,880 528,881 21,882 146,883 477,884 349,885 101,886 249,887 27,888 198,889 292,890 399,891 363,892 316,893 137,894 105,895 211,896 166,897 295,898 149,899 17,900 165,901 282,902 250,903 395,904 396,905 65,906 254,907 77,908 402,909 442,910 366,911 113,912 336,913 79,914 195,915 458,916 233,917 366,918 513,919 402,920 352,921 131,922 109,923 497,924 149,925 363,926 196,927 1,928 46,929 226,930 272,931 400,932 349,933 138,934 105,935 290,936 149,937 253,938 58,939 498,940 47,941 529,942 208,943 232,944 296,945 423,946 260,947 98,948 253,949 47,950 180,951 524,952 94,953 70,954 28,955 503,956 18,957 75,958 260,959 61,960 425,961 458,962 231,963 212,964 190,965 50,966 207,967 237,968 414,969 164,970 350,971 9,972 409,973 183,974 234,975 334,976 158,977 177,978 224,979 204,980 273,981 27,982 502,983 462,984 337,985 365,986 521,987 466,988 319,989 428,990 180,991 242,992 266,993 250,994 458,995 293,996 19,997 53,998 270,999 349,1000 13,1001 246,1002 226,1003 315,1004 53,1005 409,1006 368,1007 103,1008 364,1009 57,1010 286,1011 455,1012 320,1013 112,1014 17,1015 57,1016 137,1017 234,1018 344,1019 167,1020 529,1021 270,1022 324,1023 382,1024 4,1025 420,1026 70,1027 257,1028 444,1029 185,1030 32,1031 103,1032 261,1033 215,1034 227,1035 477,1036 431,1037 448,1038 335,1039 171,1040 165,1041 161,1042 168,1043 530,1044 409,1045 78,1046 407,1047 378,1048 412,1049 326,1050 338,1051 302,1052 106,1053 274,1054 375,1055 78,1056 44,1057 395,1058 92,1059 438,1060 75,1061 152,1062 116,1063 270,1064 332,1065 182,1066 484,1067 470,1068 142,1069 283,1070 344,1071 243,1072 183,1073 169,1074 446,1075 262,1076 425,1077 518,1078 198,1079 44,1080 383,1081 332,1082 381,1083 311,1084 434,1085 213,1086 242,1087 255,1088 530,1089 343,1090 265,1091 434,1092 229,1093 255,1094 114,1095 466,1096 477,1097 159,1098 521,1099 498,1100 8,1101 289,1102 323,1103 293,1104 527,1105 471,1106 459,1107 206,1108 431,1109 23,1110 266,1111 179,1112 66,1113 502,1114 207,1115 138,1116 286,1117 239,1118 394,1119 437,1120 60,1121 510,1122 325,1123 407,1124 197,1125 136,1126 373,1127 347,1128 441,1129 72,1130 419,1131 179,1132 305,1133 381,1134 10,1135 119,1136 288,1137 16,1138 386,1139 188,1140 241,1141 15,1142 322,1143 349,1144 181,1145 54,1146 295,1147 297,1148 335,1149 211,1150 199,1151 281,1152 397,1153 282,1154 215,1155 131,1156 7,1157 92,1158 324,1159 252,1160 201,1161 506,1162 299,1163 135,1164 98,1165 468,1166 1,1167 258,1168 377,1169 97,1170 371,1171 520,1172 426,1173 179,1174 514,1175 488,1176 238,1177 506,1178 47,1179 3931180 ],1181 4406480211182 ],1183 "output": 4406483561184 },1185 {1186 "input": [1187 [1188 699,1189 277,1190 733,1191 143,1192 496,1193 112,1194 374,1195 61,1196 228,1197 297,1198 536,1199 119,1200 671,