1482 - 划分

通过次数

提交次数

旧版界面

Time Limit : 10 秒

Memory Limit : 1024 MB

Input

Output

Examples

Input

Output

Hint

5 0
5 1 7 9 9

		</td>
		<td>

		</td>
	</tr>
	<tr>
		<td>

10 0
5 6 7 7 4 6 2 13 19 9

		</td>
		<td>

		</td>
	</tr>
	<tr>
		<td>

10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234

		</td>
		<td>

4972194419293431240859891640

		</td>
	</tr>
</tbody>

【样例 1 解释】

最优的划分方案为&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">\{5&#44;1\}&#44; \{7\}&#44; \{9\}&#44; \{9\}</span><span class="katex-html"><span class="strut" style="vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">5</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mord">1</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">7</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">9</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">9</span><span class="mclose">}</span></span></span>。由&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">5 + 1 \leq 7 \leq 9 \leq 9</span><span class="katex-html"><span class="strut" style="vertical-align:-0.08333em;"></span><span class="mord">5</span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.13597em;"></span><span class="mord">1</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.13597em;"></span><span class="mord">7</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.13597em;"></span><span class="mord">9</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut" style="vertical-align:0em;"></span><span class="mord">9</span></span></span>&nbsp;知该方案合法。

答案为&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247</span><span class="katex-html"><span class="strut" style="vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord">5</span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="vertical-align:bottom;"><span><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight" style="font-size:0.7em;"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.08333em;"></span><span class="mord"><span class="mord">7</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="vertical-align:bottom;"><span><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight" style="font-size:0.7em;"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.08333em;"></span><span class="mord"><span class="mord">9</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="vertical-align:bottom;"><span><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight" style="font-size:0.7em;"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut" style="vertical-align:0em;"></span><span class="mord"><span class="mord">9</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="vertical-align:bottom;"><span><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight" style="font-size:0.7em;"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mspace"></span><span class="mrel">=</span><span class="mspace"></span><span class="strut" style="vertical-align:0em;"></span><span class="mord">2</span><span class="mord">4</span><span class="mord">7</span></span></span>。

虽然划分方案&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">\{5\}&#44; \{1\}&#44; \{7\}&#44; \{9\}&#44; \{9\}</span><span class="katex-html"><span class="strut" style="vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">5</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">1</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">7</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">9</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">9</span><span class="mclose">}</span></span></span>&nbsp;对应的运行时间比&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">247</span><span class="katex-html"><span class="strut" style="vertical-align:0em;"></span><span class="mord">2</span><span class="mord">4</span><span class="mord">7</span></span></span>&nbsp;小，但它不是一组合法方案，因为&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">5 \gt 1</span><span class="katex-html"><span class="strut" style="vertical-align:-0.0391em;"></span><span class="mord">5</span><span class="mspace"></span><span class="mrel">&gt;</span><span class="mspace"></span><span class="strut" style="vertical-align:0em;"></span><span class="mord">1</span></span></span>。

虽然划分方案&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">\{5\}&#44; \{1&#44;7\}&#44; \{9\}&#44; \{9\}</span><span class="katex-html"><span class="strut" style="vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">5</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">1</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mord">7</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">9</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">9</span><span class="mclose">}</span></span></span>&nbsp;合法，但该方案对应的运行时间为&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">251</span><span class="katex-html"><span class="strut" style="vertical-align:0em;"></span><span class="mord">2</span><span class="mord">5</span><span class="mord">1</span></span></span>，比&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">247</span><span class="katex-html"><span class="strut" style="vertical-align:0em;"></span><span class="mord">2</span><span class="mord">4</span><span class="mord">7</span></span></span>&nbsp;大。

【样例 2 解释】

最优的划分方案为&nbsp;<span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main&#44;;"><span class="katex-mathml">\{5\}&#44; \{6\}&#44; \{7\}&#44; \{7\}&#44; \{4&#44;6&#44;2\}&#44; \{13\}&#44; \{19&#44;9\}</span><span class="katex-html"><span class="strut" style="vertical-align:-0.25em;"></span><span class="mopen">{</span><span class="mord">5</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">6</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">7</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">7</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">4</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mord">6</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mord">2</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">1</span><span class="mord">3</span><span class="mclose">}</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mopen">{</span><span class="mord">1</span><span class="mord">9</span><span class="mpunct">&#44;</span><span class="mspace"></span><span class="mord">9</span><span class="mclose">}</span></span></span>。 <br />

Source

noip2019