{"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":"78072b08-1ba0-5117-a1ee-122ac50e68c9","task_key":"ICPC~2dWorld~2dFinals--examples--2019~5fB","task_revision_id":"2","upstream_id":"2019_B","short_description":"Beautiful Bridges","config":"ICPC-World-Finals","split":"examples","body":"{\"platform\":\"atcoder\",\"question_content\":\"## Problem: Arch Bridges Construction\\n\\n### Description\\n\\nWhat connects us all? Well, it is often bridges. Since ancient times, people have been building bridges for roads, for trains, for pedestrians, and as aqueducts to transport water. It is humanity’s way of not taking inconvenient geography for an answer.\\n\\nThe company Arch Bridges Construction (ABC) specializes in—you guessed it—the construction of arch bridges. This classical style of bridge is supported by pillars that extend from the ground below the bridge. Arches between pillars distribute the bridge’s weight onto the adjacent pillars.\\n\\nThe bridges built by ABC often have pillars spaced at irregular intervals. For aesthetic reasons, ABC’s bridges always have semicircular arches. However, while a bridge arch can touch the ground, it cannot extend below the ground. This makes some pillar placements impossible.\\n\\nGiven a ground profile and a desired bridge height \\\\( h \\\\), there are usually many ways of building an arch bridge. We model the ground profile as a piecewise-linear function described by \\\\( n \\\\) key points \\\\((x_1, y_1), (x_2, y_2), \\\\ldots, (x_n, y_n)\\\\), where the x-coordinate of a point is the position along the bridge, and the y-coordinate is the elevation of the ground above sea level at this position along the bridge. The first and last pillars must be built at the first and last key points, and any intermediate pillars can be built only at these key points.\\n\\nThe cost of a bridge is the cost of its pillars (which is proportional to their heights) plus the cost of its arches (which is proportional to the amount of material used). So a bridge with \\\\( k \\\\) pillars of heights \\\\( h_1, \\\\ldots, h_k \\\\) that are separated by horizontal distances \\\\( d_1, \\\\ldots, d_{k-1} \\\\) has a total cost of:\\n\\n\\\\[\\n\\\\alpha \\\\cdot \\\\sum_{i=1}^{k} h_i + \\\\beta \\\\cdot \\\\sum_{i=1}^{k-1} d_i^2\\n\\\\]\\n\\nfor some given constants \\\\( \\\\alpha \\\\) and \\\\( \\\\beta \\\\). ABC wants to construct each bridge at the lowest possible cost.\\n\\n### Input\\n\\n- The first line of input contains four integers \\\\( n, h, \\\\alpha, \\\\) and \\\\( \\\\beta \\\\), where \\\\( 2 \\\\leq n \\\\leq 10^4 \\\\) is the number of points describing the ground profile, \\\\( 1 \\\\leq h \\\\leq 10^5 \\\\) is the desired height of the bridge above sea level, and \\\\( 1 \\\\leq \\\\alpha, \\\\beta \\\\leq 10^4 \\\\) are the cost factors as described earlier.\\n- Then follow \\\\( n \\\\) lines, the \\\\( i \\\\)-th of which contains two integers \\\\( x_i, y_i \\\\) \\\\((0 \\\\leq x_1 < x_2 < \\\\ldots < x_n \\\\leq 10^5 \\\\) and \\\\( 0 \\\\leq y_i < h)\\\\), describing the ground profile.\\n\\n### Output\\n\\n- Output the minimum cost of building a bridge from horizontal position \\\\( x_1 \\\\) to \\\\( x_n \\\\) at height \\\\( h \\\\) above sea level. If it is impossible to build any such bridge, output `impossible`.\\n\\n### Sample Input 1\\n\\n```\\n5 60 18 2\\n0 0\\n20 20\\n30 10\\n50 30\\n70 20\\n```\\n\\n### Sample Output 1\\n\\n```\\n6460\\n```\\n\\n### Sample Input 2\\n\\n```\\n4 10 1 1\\n0 0\\n1 9\\n9 9\\n10 0\\n```\\n\\n### Sample Output 2\\n\\n```\\nimpossible\\n```\",\"question_title\":\"Beautiful Bridges\"}","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":[]}