Funcia
Lv.4convex-hull-trickdpli-chao-tree

Frog Jumping Across Stones

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

N stepping stones lie in a row across a stream; stone i has height h[i]. A frog starts on stone 0 and wants to reach stone N-1. From stone i it may jump to any stone j > i in one jump, which costs

(h[j]−h[i])2+c(h[j] - h[i])^2 + c

where c is a fixed cost per jump. Return the minimum total cost to reach stone N-1.

Examples

hcresult
[1, 3, 6, 10]544
[5, 1, 5]100100
[1, 1000000]0999998000001

Example 1 — stepping on every stone costs 22+32+42+3×5=442^2 + 3^2 + 4^2 + 3 \times 5 = 44; jumping straight to the end costs 86 and 0 → 2 → 3 costs 51.

Example 2 — the fixed cost is large, so jumping 0 → 2 directly (height difference 0) costs only 100100.

Example 3 — the answer may not fit in 32 bits.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(h: int[], c: long) → long

Constraints

  • 2≤N=2 \le N = h.length ≤200,000\le 200{,}000
  • 1≤1 \le h[i] ≤1,000,000\le 1{,}000{,}000 (heights are not necessarily sorted)
  • 0≤0 \le c ≤1012\le 10^{12}

Expected complexity

Time
O(N log N)
Space
O(N)

Examples

hcExpected
[1,3,6,10]544
[5,1,5]100100
[1,1000000]0999998000001

Hint

Hint

dp[i] = min_{j<i} dp[j] + (h[i]-h[j])^2 + c is O(N2)O(N^2) as written. Expanding the square, each earlier stone j is a line y=(−2hj)x+(dp[j]+hj2)y = (-2h_j)x + (dp[j] + h_j^2) and dp[i] is the minimum of those lines at x=hix = h_i, plus hi2+ch_i^2 + c. Heights are unsorted, so use a Li Chao tree over the compressed heights (O(log⁡N)O(\log N) per insert/query), or CDQ divide and conquer with a monotone hull. Use 64-bit integers. The all-pairs DP exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.132950 msderived
Java 251344 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.