Statistics

Problem Statement for "CasketOfStar"

Problem Statement

The Casket of Star (sic) is a device in the Touhou universe. Its purpose is to generate energy rapidly. Initially it contains n stars in a row. The stars are labeled 0 through n-1 from the left to the right. You are given a int[] weight, where weight[i] is the weight of star i.


The following operation can be repeatedly used to generate energy:
  1. Choose a star x other than the very first star and the very last star.
  2. The x-th star disappears.
  3. This generates weight[x-1] * weight[x+1] units of energy.
  4. We decrease n and relabel the stars 0 through n-1 from the left to the right.



Your task is to use the device to generate as many units of energy as possible. Return the largest possible total amount of generated energy.

Definition

Class:
CasketOfStar
Method:
maxEnergy
Parameters:
int[]
Returns:
int
Method signature:
int maxEnergy(int[] weight)
(be sure your method is public)

Constraints

  • weight will contain between 3 and 50 elements, inclusive.
  • Each element in weight will be between 1 and 1,000, inclusive.

Examples

  1. {1,2,3,4}

    Returns: 12

    We have only 2 choices: Make the "2" disappear first, and "3" next. The total energy is 1*3 + 1*4 = 7. Make the "3" disappear first, and "2" next. The total energy is 2*4 + 1*4 = 12. So the answer is 12.

  2. {100,2,1,3,100}

    Returns: 10400

    We proceed as follows: {100,2,1,3,100} => {100,1,3,100} => {100,3,100} => {100,100} The total energy is 100*1 + 100*3 + 100*100 = 10400.

  3. {2,2,7,6,90,5,9}

    Returns: 1818

  4. {477,744,474,777,447,747,777,474}

    Returns: 2937051

  5. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    Returns: 13

  6. {54,64,24,24,72,33,30,40,22,17,40,21,41,64,8,46,18,65,48,32,52,54,75,5,18,37,41,22,68,42,55}

    Returns: 96202

  7. {428,507,566,692,555,344,618,218,674,697,332,433,240,453,694,264,695,263,264,351,700,691,354,560,258,181,599,477,368,509,518,401,485,323,671,201,428}

    Returns: 12714780

  8. {134,333,377,148,233,155}

    Returns: 237815

  9. {575,549,601,593,590,585,612,605,556,619,575,649,547,642}

    Returns: 4627648

  10. {671,547,393,594,655,704,376,320,711,671,500,265,638,457,468,549,485,695,252,655,262,670,450,310,716,497,619,496,301,642,332,350,675,363,253}

    Returns: 13367148

  11. {365,325,353,337,309,358,317,349,322,325,334,296,352,349,318,354,325,371,338,325,306}

    Returns: 2379637

  12. {611,213,619,592,216,558,255,461,207,663,577,679,198,632,521,416,420,651,654,620,472,507}

    Returns: 7490179

  13. {272,223,226,269,290,303,277,274}

    Returns: 457520

  14. {95,221,734,362,713,352,341,520,280,260,314,479,355}

    Returns: 2870087

  15. {379,483,521,400,506,587,486,248,390,311,440,465,405,441,375,533,452,277,475,460,572,557,489,259,486,445,497,447,283,289,503,400,559,372}

    Returns: 8269952

  16. {98,98,87,88,93,85,83,83,90,88,88,82,91,91,96,89,93,87,87,84,87,85,85,92,92,90,82,94,85,88,92,84,94,87,89,85,96,85,98,87,95}

    Returns: 343128

  17. {569,750,216,689,410,672,401,198,270,727,171,187,482,139,94,211,404,693,105,105,309,237,668,549,540,573,466,121,160,408,399,270,595,370,217,132,204,115}

    Returns: 10674721

  18. {258,347,225,302}

    Returns: 182710

  19. {804,789,804,773,806,804,763,754,778,766,799,753,779,768,776,745,772,748,767,787,800,782,752,758,786,800,768,757,775,748,800,780,793,752,803,791,774,774,780,788,800,772,748}

    Returns: 25775864

  20. {944,954,955,951,937,972,961,950,943,952,937,980,972,943}

    Returns: 11149064

  21. {760,691,673,844,829,499,518,674}

    Returns: 3355092

  22. {164,289,209,354,226,308,357,477,191,277,551,308,188,492,420,632,712,238,303,263,177,723,671,234,496,162,501,550,265,284,449,295,257,607}

    Returns: 8686576

  23. {849,770,923,363,904,492,796,606,594,682,591,746,325,270,613,300,577,514,423,308,612,855,627,417,587}

    Returns: 12782043

  24. {796,940,932,758,829,842,820,817,884,838,819,935,910,766,750,804,923,888,775,804,933,869,838,851,787,928,771}

    Returns: 20010894

  25. {419,664,509,696,534,230,799,236,405,251,329,775,464,447,829,281,551,391,250,427,488,248,221,607,614,827,630,821,771,380,572,307,824,446,412,583,697,259,314,701,347,415,675,606,593}

    Returns: 20153330

  26. {442,443,783,936,675,520,937,611,413,771,634,867,691,804,655,373,464,719,713}

    Returns: 10401350

  27. {902,961,927,825,954}

    Returns: 2661660

  28. {687,480,542,589,683,668,630,508,553,586,462,676,516,672,500,431,432,686,551,490,690,655,677,648,529,638,632,682,569,655,596,511,535,657,692,697,655,518}

    Returns: 15471373

  29. {114,219,705,370,715,431,359,438,702,718,319,161,569,715,109,629,492,196,415,79,401}

    Returns: 6527401

  30. {726,380,450,437,491,687,458,417,689,508,500,669,447,366,675,580,768,386,710,43,523,428,841,698,448,112,182,594,214,161,406,363,577,641,169,409,162,754,223,710,496,597,247,593}

    Returns: 18204371

  31. {381,403,421,478,403,325,300,306,357,363,425,366,342,359,391,485,384,448,380,450,304,409,306,476,433,356,420,395,398,339,460,378,466,335,379,382,338,301,456,358,302,478,428,340,467}

    Returns: 8415943

  32. {318,309,337,296,294,317,304,294,298,296,298,328,337,316,338,304,339,334,299,337,299,312,334,330,322,333,331,288,336,295,331,285,301,289,332}

    Returns: 3588902

  33. {546,577,686,298,340,683,597,323,474,608,511,392,563,433,479,479,568,408,531,344,451,379,301,554,530,363,311,430,669,417,323,526,593,672}

    Returns: 10906402

  34. {511,495,522,582,270,644,371,505,306,291,380,305,410,536}

    Returns: 3392788

  35. {668,765,785,747,755,660,716,776,761,723,667,742,618,689,716,754,726,705,750,730,650,694,676}

    Returns: 11668747

  36. {678,699,673,693,703,699,705,703,670,664,668,694,700,687,701,697,668,690,682,696,681,700,699,678,663,689,678,700}

    Returns: 12640500

  37. {668,420,718,696,202,119,192,227,119,331,466,442,238,795,292,575,218}

    Returns: 4855507

  38. {304,307,313,307,314,300,305,313,299,297,298,309,300,314,311,300,310,302,300,295,296,312,304,309,314,301,301,310,304,308,312,313,303,305,310,298,308,314,311,305,298,299,303,307,296}

    Returns: 4138369

  39. {690,642,626}

    Returns: 431940

  40. {268,103,87}

    Returns: 23316

  41. {21,273,281,263,78,417,459,386,537,533,130,430,46,210,379,87,169,255,381,341,12,540,26,165,340,21,341,410,49,29,571,165,274,509,567,147,393,396,513,350,338,155,135,159,226,473,159,346,117,205}

    Returns: 8671102

  42. {331,339,232,236,317,275,328,311,327,329,310,250,315,223,229,299,239,284,218,303,245,271,212,286,226,269,255,310,314,250,241,272,219,284,276,249,321,334,248,320,295,293,278,263,326,248,233,310,292,319}

    Returns: 4639980

  43. {947,948,918,887,929,840,826,817,803,860,928,893,821,824,909,804,876,787,810,865,914,860,823,911,863,837,819,846,780,840,940,828}

    Returns: 24439378

  44. {68,927,215,308,539,276,162,355,548,176,239,546,517,721,449,765,70,342,844,184,532,66,484,325,152,428,457,685,141,274,579,380,292,304,465,173,131,761,181,440,148,220,171,322,165,219,490,435,466,874}

    Returns: 18407053

  45. {213,217,194,196,222,199,212,192,226,202,196,223,207,227,190,194,219,219,217,188,196,209,223,201,219,223,193,220,201,223,215,211,225,208,195,190,217}

    Returns: 1690917

  46. {782,811,762,779,874,692,880,808,674,849,691,733,860,776,837,766,675,745,848,744,778,795,852,844,792,728,876,848,861,674,834,841,885,734,864,717,707,672,737,785,711,863,686}

    Returns: 29006896

  47. {621,445,362,659,688,395,806,463,566,638,631,774,439,766,476,652,740,322,534,796,388,511,343}

    Returns: 10375558

  48. {457,470,453,455,452,464,450,449,449,458,448,467,466,451,469,450,451,466,459,451,466,461,452,460,457,465,453,470,464,453,468,448,462,451,455,465,448,463,448,449,468,458,463,463,459,451,451,448,448,462}

    Returns: 10358879

  49. {837,825,519,867,811,789,674,904,801,791,874,899,991,897,837,700,808,893,711,912,663,586,689,911,899,651,858,514,951,987,598,668,695,913,987}

    Returns: 27011685

  50. {226,252,353,315,307,127,483,58,180}

    Returns: 829419

  51. {267,462,479,705,314,283,713,452,743,827,439,208,524,214,785,179,288,460,213,183,335,391,158,783,694,819,777,670,804,508}

    Returns: 12201391

  52. {348,612,561,351,519,533,384,642,747,595,696,381,470,509,697,560,721,629,624,634,513,378,410,404,598,513,519,669,558,438,722,403,435,623,425,359,677}

    Returns: 14487221

  53. {693,674,663,676,683,680,703,667,678,713}

    Returns: 3879070

  54. {304,342,318,342,311,331,296,343,345,329,346,330,298,300,310,359,345,318,350,323,340,333,302,343,313,338,341,347,348,336,307,302,327,351,342,320,356,347,347,355,318}

    Returns: 4646739

  55. {441,759,468}

    Returns: 206388

  56. {6,8,9,9,5,6}

    Returns: 216

  57. {3,2,5,3,3,4,1}

    Returns: 65

  58. {4,4,4,4,4,4,4,4,4,4,4,4,4,4,4}

    Returns: 208

  59. {5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5}

    Returns: 500

  60. {1,2,2,1,2,1,1}

    Returns: 13

  61. {8,5,5,5,5,10,8,5,5,7,10,7,10,10}

    Returns: 890

  62. {5,7,6,7,5,5,7,4,3,5,3,5,6,3,3,5,4,3,3,5,5,5,6,3,3,4,5,7,7,3,7,5,4,7,3,3,3,7,6}

    Returns: 1344

  63. {8,8,6,7,7,7,7,8,8,7,7,6,8,8,7,8,8,8,8,7}

    Returns: 1096

  64. {3,3,4,5,5,3,3,5,5,4,4,5,3,3,3,4,4,5}

    Returns: 330

  65. {4,4,5,5,5,4,5,4,4,4,4,4,5,4,4,5,4,5,4,4,5,5,4,5,5,4,5,5,5,4,5,4,5,4,5,5,5,4,5,4,4,5,5,5,4,4,5}

    Returns: 1075

  66. {10,10,9,7,6,5,9,9,3,7,3,6,10,3,3,8,9,8,6,4,6,4,9,10,4,8,7,6,4,5,7,6,5,7,5,4,7,10,8,6,4,3,4,4,8,8,9,10,10}

    Returns: 3310

  67. {2,4,1,4,2,4,4,1,1,3,3,2,1,3,3,2,1,2,1,1,3,3,1,2}

    Returns: 214

  68. {1,2,1,1,2,1,1,1,2,1,2,2,2,2,2,2}

    Returns: 48

  69. {8,8,8,8,9,9,8,8,9,8,9,9,9,8,8,9,9,9,8,9,8,9,9,9,8,8,8,9,9,9,9,8,8,8,9,8,9,9,9}

    Returns: 2907

  70. {4,6,4,7}

    Returns: 70

  71. {4,6,8,7,8,4,6,7,4,4,7,7,7,7,5,6,7,5,8,7,7,4,8,6,4,4,4,5}

    Returns: 1276

  72. {4,1,3,5,2,3,4,6,3,8,7,3,5,1,5,1,7,3,5,6,2,3,7,2,5,6,6,5,8,8,6,2,4,2,7,2,1,2,7}

    Returns: 1422

  73. {8,8,8,9,8,9,9,8,9,9,9,8,8,9,8,8,9,9,9,8,9,9,8,8,8,9,8,8,8,8,9,9,9,8,9,9,9,9,9,9}

    Returns: 2988

  74. {8,9,9,7,6,7,7,7,9,7,8,6,7,9,8,7,8,8,6,8,9,7,6,7,6,9,9,6,7,7,8,6,8,6,7}

    Returns: 2278

  75. {4,2,2,4,3,2,2,2,2,3,4,2,3,3,3}

    Returns: 148

  76. {982,994,945,947,983,982,964,939,992,995,992,958,993,976,988,975,937,956,985,949,971,965,991,993,968,995,992,954,951,956,996,938,980,971,975,948,945,974,972,981}

    Returns: 36946840

  77. {917,918,940,955,988,964,945,931,930,992,930,931,997,998,957,951,968,962,996,956,987,952,943,942,984,930,922,919,920,992,953,950,965,993,940,926,947,978,921,982}

    Returns: 36321482

  78. {929,969,939,988,901,956,939,955,987,988,956,929,992,965,927,935,919,916,924,902,920,916,979,975,923,944,952,936,988,918,957,915,970,919,970,952,938,907,949,905,940,906,909,915,927}

    Returns: 40227129

  79. {935,930,947,951,937,953,939,956,929,943,946,944,943,943,944,952,931,928,946,944,955,950,933,954,927,956,936,954,931,945,951,925,939,927,956,928,945,935,943,957,958}

    Returns: 35341426

  80. {936,934,935,936,935,934,934,935,935,934,934,934,936,934,936,934,935,936,936,936,935,934,936,935,936,936,935,935,935,936,935,935,935,936,935,935,936,934,936,934,936,936,934,934,936,935,936,934,934}

    Returns: 41153112

  81. {935,942,935,942,938,937,938,942,937,936,942,941,940,940,936,940,937,940,939,935,936,936,937,940,935,940,938,935,935,935,940,938,942,940,940,939,942,936,940,942,941,941,941,941,935}

    Returns: 38039905

  82. {965,966,977,957,975,964,975,975,956,973,955,970,958,955,966,977,955,973,957,959,959,975,975,975,980,965,961,971,962,974,971,976,955,965,954,963,979,975,977,980,955,954,975,976}

    Returns: 39891356

  83. {920,916,920,919,918,919,918,916,919,916,920,919,920,917,917,919,916,917,916,916,920,916,920,919,920,918,919,919,917,918,920,916,917,917,919,917,916,919,917,917,917,919,917,920,917}

    Returns: 36340013

  84. {924,917,919,971,954,942,947,938,965,931,956,959,939,914,956,930,944,920,952,946,941,969,946,920,915,912,967,948,925,953,954,964,940,968,905,951,909,974,915,916,905,944,910,969}

    Returns: 38627917

  85. {960,940,946,966,955,948,955,948,932,945,944,941,955,955,940,932,940,945,934,943,954,927,947,940,941,944,949,954,933,950,929,933,943,934,944,941,926,941,926,945,927}

    Returns: 35483046

  86. {943,943,927,940,943,932,941,930,942,931,933,942,942,941,938,933,933,934,940,926,940,932,932,941,931,933,928,942,939,927,934,934,937,933,928,939,927,935,934,935,927,927,933,925,943,930,935,929}

    Returns: 40624654

  87. {973,961,978,965,974,947,978,958,966,944,953,989,994,947,983,992,993,970,951,991,994,993,956,983,962,960,995,947,975,966,967,953,971,966,990,963,990,940,970,971,980,940,956,983}

    Returns: 40709252

  88. {967,964,928,968,956,951,930,953,963,969,937,939,968,947,951,959,944,942,928,971,971,938,949,953,947,937,963,928,931,922,938,943,969,967,929,935,922,955,931,936,935,941,928,947,955,967,927,970,924}

    Returns: 43360289

  89. {948,915,937,930,940,924,926,914,942,945,924,938,918,917,938,923,939,941,917,941,948,949,918,944,925,933,914,922,945,941,921,918,948,927,948,926,944,947,939,929,933,949}

    Returns: 35560589

  90. {971,970,970,971,971,970,970,970,970,971,971,971,970,970,971,970,970,971,970,971,971,971,971,970,971,970,971,970,971,971,971,971,970,970,971,971,971,970,971,971,971,971,971,970,971}

    Returns: 40535366

  91. {929,959,929,955,924,958,949,941,914,954,939,922,952,928,956,959,951,955,919,936,922,917,926,931,919,925,932,917,946,954,949,940,959,927,951,933,919,959,944,943,924,931}

    Returns: 36139643

  92. {934,938,962,971,927,928,971,953,980,957,935,967,933,985,959,929,932,987,947,947,946,991,956,988,944,947,946,947,983,978,946,975,963,968,970,929,932,976,954,963,942,926}

    Returns: 37888144

  93. {929,948,945,948,921,950,931,939,950,932,917,935,952,951,961,930,951,947,959,933,945,938,947,922,942,938,928,942,917,928,933,957,924,928,961,942,939,928,934,958,935,954,960,918,947,950,951,945,947,928}

    Returns: 43439869

  94. {974,974,974,974,974,973,973,974,973,973,973,973,974,974,973,974,973,974,974,973,974,974,974,973,973,974,973,973,974,973,974,974,973,974,973,974,973,974,974,974,974}

    Returns: 36992520

  95. {940,929,936,935,940,932,925,933,932,924,929,931,936,934,937,942,926,927,935,935,925,923,934,923,930,934,923,928,939,931,926,941,941,928,930,942,929,937,925,928,925}

    Returns: 34255220

  96. {201, 841, 368, 221, 394, 175, 556, 322, 481, 813, 883, 304, 881, 188, 236, 150, 414, 764, 37, 68, 308, 217, 260, 366, 897, 176, 95, 735, 951, 182, 572, 540, 59, 146, 354, 989, 768, 438, 438, 792, 868, 833, 191, 917, 946, 24, 530, 187, 215, 1 }

    Returns: 24144660

  97. {10, 7, 6, 2, 1, 10, 10, 7, 9, 4, 5, 9, 5, 10, 10, 3, 6, 6, 4, 4, 4, 8, 5, 4, 9, 1, 9, 9, 1, 7, 9, 2, 10, 9, 10, 8, 3, 3, 9, 3, 9, 10, 1, 8, 9, 2, 6, 9, 7, 2 }

    Returns: 3693

  98. {589, 848, 314, 255, 905, 435, 607, 979, 749, 570, 474, 318, 264, 563, 235, 593, 263, 597, 190, 377, 333, 311, 100, 675, 960, 299, 154, 438, 303, 206, 855, 801, 7, 364, 956, 690, 821, 76, 835, 416, 661, 478, 738, 478, 593, 221 }

    Returns: 23704925

  99. {1, 5, 5, 5, 5, 5, 100, 1000, 100, 1 }

    Returns: 27001

  100. {5, 100, 30, 1, 1, 1, 30, 100, 5 }

    Returns: 14485

  101. {212, 743, 379, 313, 343, 157, 571, 332, 482, 799, 879, 299, 890, 201, 237, 149, 409, 769, 41 }

    Returns: 6722359

  102. {963, 465, 706, 146, 282, 828, 962, 492 }

    Returns: 3661104

  103. {3, 1, 2, 5, 4 }

    Returns: 33

  104. {5, 1, 7, 19, 12 }

    Returns: 190

  105. {809, 974, 742, 352, 372, 185, 750, 536, 642, 572, 544, 919, 985, 200, 877, 194, 371, 606, 99, 374, 347, 632, 145, 84, 825, 293, 159, 761, 330, 299, 584, 348, 767, 782, 917, 233, 327, 247, 695, 474, 796, 904, 440, 725, 303, 35, 566, 809, 937, 290 }

    Returns: 27454956

  106. {405, 454, 446, 125, 706, 941, 613, 406, 77 }

    Returns: 2120542

  107. {1, 3, 8, 3, 1 }

    Returns: 17

  108. {384, 887, 778, 916, 794, 336, 387, 493, 650, 422, 363, 28, 691, 60, 764, 927, 541, 427, 173, 737, 212, 369, 568, 430, 783, 531, 863, 124, 68, 136, 930, 803, 23, 59, 70, 168, 394, 457, 12, 43, 230, 374, 422, 920, 785, 538, 199, 325, 316, 371 }

    Returns: 22047735

  109. {4, 1, 5, 8, 5, 1, 4 }

    Returns: 120

  110. {5, 24, 10, 2, 3 }

    Returns: 135

  111. {5, 2, 2, 7, 9 }

    Returns: 94

  112. {13, 12, 51, 61, 12, 51, 81, 17, 15, 76, 41, 61, 62, 63, 23 }

    Returns: 44681

  113. {1, 3, 5, 3, 1, 2, 5, 1 }

    Returns: 67

  114. {1, 15, 100, 7, 1, 14 }

    Returns: 1724

  115. {1, 13, 100, 13, 1, 1, 100 }

    Returns: 12800

  116. {5, 2, 5, 20, 10 }

    Returns: 190

  117. {824, 840, 75, 511, 803, 323, 146, 923, 237, 834 }

    Returns: 5135928

  118. {45, 67, 89, 24, 78, 98, 456, 678, 267, 9, 5, 3, 6, 78, 234, 876, 23, 5, 67, 98, 13, 5, 89, 23, 68, 123, 34, 345, 56, 567, 78, 890, 98, 24, 76, 24, 97, 678, 34, 123, 839, 538, 4, 6, 89, 3, 4, 5 }

    Returns: 8076363

  119. {217, 914, 489, 289, 952, 873, 300, 938, 120, 199, 601, 770, 203, 278, 252, 215, 795, 734, 781, 523, 295, 389, 150, 928, 333, 42, 227, 962, 280, 924, 92, 925, 779, 239, 686, 466, 126, 344, 259, 645, 192, 875, 703, 370, 199, 241, 597, 423, 475, 334 }

    Returns: 26377278

  120. {10, 1, 1, 3, 10, 4, 1 }

    Returns: 190

  121. {10, 20, 100, 60, 10 }

    Returns: 2100

  122. {100, 1000, 100, 1, 99 }

    Returns: 118800

  123. {675, 76, 67, 466, 830 }

    Returns: 920025

  124. {92, 5, 3, 54, 93 }

    Returns: 13800

  125. {3, 4, 5, 4, 3 }

    Returns: 39

  126. {100, 1, 1, 3, 150 }

    Returns: 15400

  127. {634, 573, 844, 257, 76, 715, 327, 496, 354, 827, 321, 119, 517, 548, 935, 254, 667, 490, 302, 667, 518, 309, 227, 78, 866, 162, 880, 75, 426, 807, 407, 608, 939, 712, 411, 200, 859, 746, 516, 531, 703, 30, 295, 280, 901, 850, 312, 684, 465, 65 }

    Returns: 26367021

  128. {4, 3, 4, 1, 1, 10 }

    Returns: 120

  129. {5, 1, 1, 3, 4, 3 }

    Returns: 55

  130. {999, 348, 899, 928, 958, 234, 547, 574, 938, 478, 935, 297, 950, 968, 394, 928, 43, 910, 438, 991, 837, 947, 948, 273, 485, 938, 489, 958, 839, 948, 273, 129, 947, 832, 917, 247, 938, 172, 937, 172, 475, 55, 923, 473, 192, 387, 918, 736, 493, 999 }

    Returns: 39923657

  131. {6, 4, 2, 3, 5 }

    Returns: 62

  132. {310, 617, 936, 452, 601, 250, 520, 557, 799, 304, 225, 9, 845, 610, 990, 703, 196, 486, 94, 344, 524, 588, 315, 504, 449, 201, 459, 619, 581, 797, 799, 282, 590, 799, 10, 158, 473, 623, 539, 293, 39, 180, 191, 658, 959, 192, 816, 889, 157, 512 }

    Returns: 24717175

  133. {100, 3, 1, 2, 100 }

    Returns: 10400

  134. {1, 2, 7, 4, 1, 2, 3 }

    Returns: 53

  135. {898, 875, 534, 126, 416, 31, 748, 161, 343, 202, 647, 306, 858, 87, 714, 282, 348, 26, 825, 178, 654, 190, 64, 1, 877, 883, 402, 134, 671, 678, 358, 920, 792, 258, 279, 276, 904, 454, 860, 103 }

    Returns: 20390957

  136. {544, 474, 354, 216, 531, 475, 419, 137, 763, 117, 640 }

    Returns: 3158565

  137. {10, 5, 1, 3, 4, 8, 2, 9, 6, 7 }

    Returns: 460

  138. {1, 14, 59, 79, 66, 8, 78, 1, 59, 40 }

    Returns: 27014

  139. {974, 980, 983, 999, 975, 956, 967, 986, 995, 952, 977, 988, 981, 976, 963, 989, 979, 962, 953, 961, 993, 966, 991, 972, 994, 973, 992, 970, 957, 964, 960, 982, 997, 958, 990, 965, 1000, 959, 985, 968, 978, 998, 971, 987, 984, 969, 955, 951, 954, 996 }

    Returns: 46991551

  140. {230, 39, 125, 600, 310, 380, 200, 852, 665, 291 }

    Returns: 1906360

  141. {747, 600, 777, 474, 200, 501 }

    Returns: 1581417

  142. {111, 1, 1, 33, 111, 33, 1 }

    Returns: 19869

  143. {733, 493, 483, 791, 534, 224, 220, 284, 277, 168, 737, 886, 256, 77, 596, 693, 497, 112, 135, 445, 619, 854, 995, 478, 813, 736, 512, 296, 845, 375, 598, 298, 586, 81, 89, 120, 304, 308, 403, 299, 194, 140, 186, 169, 935, 500, 580, 151, 330, 714 }

    Returns: 21847837

  144. {521, 352, 5, 235, 678, 892 }

    Returns: 1139346

  145. {812, 204, 281, 512, 119, 691, 809, 246, 445, 992, 803, 382, 949, 723, 215, 921, 869, 765, 225, 6, 230, 774, 144, 939, 831, 344, 880, 84, 856, 727, 661, 82, 430, 570, 604, 169, 787, 666, 228, 586, 187, 960, 429, 736, 75, 997, 180, 257, 472, 162 }

    Returns: 30564642

  146. {69, 38, 29, 46, 72 }

    Returns: 10143

  147. {952, 525, 186, 195, 489, 801, 475, 900, 728, 861, 143, 377, 821, 373, 635, 219, 652, 286, 969, 1, 981, 230, 190, 980, 332, 897, 688, 566, 675, 879, 652, 411, 51, 578, 676, 343, 281, 887, 165, 431, 728, 158, 27, 849, 641, 822, 71, 480, 778, 906 }

    Returns: 30940850

  148. {9, 1, 10, 99, 10, 1, 9 }

    Returns: 2061

  149. {1, 2, 7, 10, 3, 2, 1 }

    Returns: 61

  150. {6, 1, 5, 9, 8 }

    Returns: 132

  151. {10, 1, 11, 100, 11, 1, 10 }

    Returns: 2320

  152. {720, 626, 287, 354, 324, 45, 513, 224, 404, 538, 661, 643, 678, 275, 663, 731, 60, 181, 506, 533, 675, 38, 644, 756, 454, 299, 461, 445, 43, 270, 450, 704, 129, 666, 68, 495, 531, 528, 171, 7, 141, 588, 154, 331, 467, 312, 57, 104, 57, 701 }

    Returns: 16607808

  153. {100, 98, 2, 1, 3, 100 }

    Returns: 20192

  154. {4, 1, 1, 5, 6, 5, 5, 5 }

    Returns: 130

  155. {968, 530, 474, 579, 581, 873, 25, 639, 54, 830, 271, 216, 583, 963, 658, 624, 728, 710, 791, 533, 304, 470, 640, 948, 401, 934, 970, 919, 567, 386, 548, 237, 573, 848, 711, 604, 20, 20, 910, 652, 668, 903, 164, 937, 66, 426, 489, 932, 745, 878 }

    Returns: 32254576

  156. {668, 300, 36, 895, 704, 812, 323 }

    Returns: 2351280

  157. {17, 4, 1, 2, 16 }

    Returns: 352

  158. {5, 11, 3, 1, 3 }

    Returns: 59

  159. {257, 386, 2, 492, 122, 108, 651, 903, 813, 517, 478, 387, 458, 295, 775, 753, 799, 974, 271, 246, 914, 548, 337, 462, 448, 716, 909, 948, 608, 790, 681, 866, 175, 684, 47, 297, 482, 699, 200, 295, 906, 368, 372, 363, 664, 838, 806, 462, 811, 76 }

    Returns: 26582372

  160. {1, 5, 10, 3, 1, 3 }

    Returns: 58

  161. {4, 15, 4, 1, 3 }

    Returns: 72

  162. {336, 263, 42, 39, 774, 619, 256, 449, 391, 557, 355, 603, 500, 768, 434, 106, 989, 52, 427, 400, 151, 83, 501, 886, 228, 624, 528, 586, 719, 334, 874, 54, 596, 267, 445, 369, 238, 52, 169, 980, 960, 523, 935, 459, 290, 368, 916, 630, 420, 342 }

    Returns: 24504832

  163. {100, 20, 1, 6, 1, 1, 100 }

    Returns: 12820

  164. {1, 100, 100, 2, 1, 100, 1 }

    Returns: 20301

  165. {100, 5, 1, 2, 100 }

    Returns: 10600

  166. {20, 300, 20, 1, 1, 10, 1 }

    Returns: 3920

  167. {10, 20, 8, 1, 8 }

    Returns: 304

  168. {10, 1, 10, 99, 10, 1, 10 }

    Returns: 2280

  169. {1, 2, 5, 3, 1, 1 }

    Returns: 16

  170. {42, 468, 335, 501, 170, 725, 479, 359, 963, 465, 706, 146, 282, 828, 962, 492, 996, 943, 828, 437, 392, 605, 903, 154, 293, 383, 422, 717, 719, 896, 448, 727, 772, 539, 870, 913, 668, 300, 36, 895, 704, 812, 323, 334, 674, 665, 142, 712, 254, 869 }

    Returns: 30098989

  171. {266, 123, 826, 697, 130, 768, 101, 111, 400, 550, 557, 301, 75, 102, 424, 983, 749, 27, 639, 671, 133, 196, 487, 776, 57, 107, 523, 781, 174, 763, 176, 486, 258, 167, 401, 472, 696, 613, 95, 170, 785, 142, 578, 642, 670, 585, 644, 578, 457, 134 }

    Returns: 21965001

  172. {312, 23, 321, 14, 543, 32, 432, 2, 43, 532, 11, 11, 321, 11, 312, 45, 543, 1, 53, 1, 543, 543, 545, 55, 444, 33, 23, 12, 4, 5, 6, 4, 77, 66, 55, 55, 33, 22, 565, 33, 55, 22, 22 }

    Returns: 5276808

  173. {3, 8, 5, 1, 1, 14 }

    Returns: 238

  174. {828, 360, 709, 472, 653, 144, 832, 616, 836, 196, 66, 944, 55, 644, 489, 355, 532, 499, 86, 639, 725, 543, 849, 441, 109, 742, 453, 759, 897, 875, 976, 231, 687, 703, 564, 988, 421, 20, 361, 854, 99, 882, 106, 438, 214, 593, 987, 536, 35, 598 }

    Returns: 30397093

  175. {1, 2, 2, 1, 1, 2, 2, 1 }

    Returns: 17

  176. {634, 885, 295, 386, 609, 486, 508, 427, 143, 92, 296, 76, 881, 572, 408, 639, 677, 707, 304, 799, 632, 722, 727, 128, 892, 738, 491, 614, 928, 267, 816, 691, 637, 944, 874, 59, 55, 580, 244, 195, 645, 937, 265, 987, 432, 62, 207, 147, 969, 779 }

    Returns: 28416054

  177. {6, 100, 17, 1, 3 }

    Returns: 418

  178. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    Returns: 58800

  179. {5, 20, 5, 1, 3 }

    Returns: 95

  180. {1, 4, 15, 4, 1 }

    Returns: 31

  181. {4, 1, 3, 9, 9 }

    Returns: 84

  182. {12, 9, 3, 2, 8 }

    Returns: 192

  183. {3, 7, 5, 2, 2 }

    Returns: 34

  184. {1, 2, 2, 1, 1, 2, 1 }

    Returns: 13

  185. {12, 101, 12, 1, 11 }

    Returns: 1375

  186. {6, 1, 10, 90, 10 }

    Returns: 690

  187. {7, 1, 3, 5, 9 }

    Returns: 119

  188. {1000, 1, 1, 1, 1, 1, 1, 1, 1, 1000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000 }

    Returns: 3015000

  189. {6, 7, 3, 1, 4 }

    Returns: 64

  190. {1000, 1, 1, 2, 1000, 501 }

    Returns: 1504000

  191. {4, 1, 5, 9, 5 }

    Returns: 76

  192. {1, 2, 5, 3, 1 }

    Returns: 11

  193. {101, 50, 2, 1, 100 }

    Returns: 15300

  194. {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 48000000

  195. {1, 2, 3 }

    Returns: 3

  196. {10, 1, 10, 20, 11 }

    Returns: 410

  197. {882, 215, 433, 988, 982, 478, 62, 348, 931, 921, 540, 564, 5, 730, 901, 500, 741, 254, 647, 368, 67, 209, 191, 324, 116, 467, 998, 412, 652, 941, 349, 879, 486, 793, 437, 594, 650, 318, 399, 751, 980, 323, 972, 585, 744, 60, 490, 326, 921, 991 }

    Returns: 31715199

  198. {100, 2, 1, 3, 101 }

    Returns: 10500

  199. {5, 50, 10, 1, 5 }

    Returns: 325

  200. {1, 4, 15, 4, 1, 3, 1 }

    Returns: 91

  201. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 5, 7, 18, 29, 49, 35, 31, 49, 68, 54, 593, 139, 438, 48, 3, 6, 3, 7, 1, 5, 89, 3, 6, 2, 7, 2, 7, 2, 5, 8, 2, 78, 35, 674, 134, 1000, 935, 198, 400 }

    Returns: 3838789

  202. {1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1, 1, 3, 8, 3, 1 }

    Returns: 1489

  203. {42, 468, 335, 501, 170, 725, 479, 359 }

    Returns: 1388765

  204. {1, 100, 99, 100, 99, 100, 100, 99, 99, 100, 100, 99, 99, 98, 99, 100, 100, 99, 99, 100, 100, 100, 100, 100, 99, 99, 99, 99, 99, 100, 1, 1 }

    Returns: 269202

  205. {2, 4, 2, 1, 2 }

    Returns: 16

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: