{"kind":"task","effective_mode":"full","benchmark":{"kind":"benchmark","effective_mode":"full","slug":"hlce","formal_name":"Humanity's Last Code Exam","introduction":"Humanity's Last Code Exam evaluates problem solving and code generation using ICPC World Finals and IOI problems. The project describes 235 problems; this import selects its public ICPC dataset of 146 problems.","introduction_ja":"","introduction_en":"","category":"Category not supplied","task_count":null,"acquisition_status":"Acquisition status not supplied","official_url":"https://humanity-s-last-code-exam.github.io/website/","indexing_mode":"noindex","profile":{"resources":[],"task_format":"","scoring":"","metric":"","size":"","answer_access":"","license":"","citation":"","maintainer":"","released":"","why_hard":"","related":[]}},"task_id":"969f29df-b4b1-57c1-a29d-89a80412767b","task_key":"ICPC~2dWorld~2dFinals--examples--2017~5fF","task_revision_id":"3","upstream_id":"2017_F","short_description":"Posterize","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"**Problem Description**\\n\\nPixels in a digital picture can be represented with three integers in the range 0 to 255 that indicate the intensity of the red, green, and blue colors. To compress an image or to create an artistic effect, many photo-editing tools include a “posterize” operation which works as follows. Each color channel is examined separately; this problem focuses only on the red channel. Rather than allow all integers from 0 to 255 for the red channel, a posterized image allows at most \\\\( k \\\\) integers from this range. Each pixel’s original red intensity is replaced with the nearest of the allowed integers. The photo-editing tool selects a set of \\\\( k \\\\) integers that minimizes the sum of the squared errors introduced across all pixels in the original image. If there are \\\\( n \\\\) pixels that have original red values \\\\( r_1, \\\\ldots, r_n \\\\), and \\\\( k \\\\) allowed integers \\\\( v_1, \\\\ldots, v_k \\\\), the sum of squared errors is defined as\\n\\n\\\\[\\n\\\\sum_{i=1}^{n} \\\\min_{1 \\\\leq j \\\\leq k} (r_i - v_j)^2\\n\\\\]\\n\\nYour task is to compute the minimum achievable sum of squared errors, given parameter \\\\( k \\\\) and a description of the red intensities of an image’s pixels.\\n\\n### Input\\n\\nThe first line of the input contains two integers \\\\( d \\\\) (1 ≤ \\\\( d \\\\) ≤ 256), the number of distinct red values that occur in the original image, and \\\\( k \\\\) (1 ≤ \\\\( k \\\\) ≤ \\\\( d \\\\)), the number of distinct red values allowed in the posterized image. The remaining \\\\( d \\\\) lines indicate the number of pixels of the image having various red values. Each such line contains two integers \\\\( r \\\\) (0 ≤ \\\\( r \\\\) ≤ 255) and \\\\( p \\\\) (1 ≤ \\\\( p \\\\) ≤ \\\\( 2^{26} \\\\)), where \\\\( r \\\\) is a red intensity value and \\\\( p \\\\) is the number of pixels having red intensity \\\\( r \\\\). Those \\\\( d \\\\) lines are given in increasing order of red value.\\n\\n### Output\\n\\nDisplay the sum of the squared errors for an optimally chosen set of \\\\( k \\\\) allowed integer values.\\n\\n### Sample Input 1\\n\\n```\\n2 1\\n50 20000\\n150 10000\\n```\\n\\n### Sample Output 1\\n\\n```\\n66670000\\n```\\n\\n### Sample Input 2\\n\\n```\\n2 2\\n50 20000\\n150 10000\\n```\\n\\n### Sample Output 2\\n\\n```\\n0\\n```\\n\\n### Sample Input 3\\n\\n```\\n4 2\\n0 30000\\n25 30000\\n50 30000\\n255 30000\\n```\\n\\n### Sample Output 3\\n\\n```\\n37500000\\n```\",\"question_title\":\"Posterize\"}","display_format":"text","language":"","answer_status":"published","assets":[],"source_url":"https://humanity-s-last-code-exam.github.io/website/","history":"initial import","indexing_mode":"noindex","subproblems":[],"grids":[]}