Merge operations for minimum travel time

impl Solution {
  pub fn min_travel_time(
    _l: i32,
    n: i32,
    k: i32,
    position: Vec<i32>,
    time: Vec<i32>,
  ) -> i32 {
    let n = n as usize;
    let k = k as usize;

    // After exactly k merges, we have n-k signs remaining (including endpoints 0 and n-1).
    // We need to choose which n-1-k internal signs to keep (we keep exactly n-2-k of the n-2 internal signs).
    //
    // Key insight on merge semantics:
    // When signs i..=j-1 are all merged into sign j:
    //   - time at sign j becomes sum(time[i..=j])
    //   - The segment from sign (i-1) to sign j costs: (position[j]-position[i-1]) * time[i-1]
    //     (because time[i-1] is the rate for the segment FROM i-1, which is unchanged)
    //   - The rate FOR the segment starting at j (going to j+1) = sum(time[i..=j])
    //
    // DP: dp[i][j] = minimum travel cost from position 0 to position[i] with exactly j merges
    //   made on signs in (0..i) (internal signs only; endpoints are never merged neighbors here).
    //
    // Actually: we view it as choosing a subsequence of signs to keep.
    // Say we keep signs s_0=0, s_1, s_2, ..., s_{m-1}=n-1 where m = n-k.
    // The cost is sum_{t=0}^{m-2} (position[s_{t+1}] - position[s_t]) * accumulated_time_at_s_{t+1}
    // Wait, what is accumulated_time_at_s_{t+1}?
    //
    // After merging all signs between s_t and s_{t+1} (i.e., signs s_t+1,...,s_{t+1}-1 merged into s_{t+1}):
    //   accumulated_time_at_s_{t+1} = sum(time[s_t+1 .. s_{t+1}])
    //   (the merge chain: s_t+1 merged into s_t+2, that merged into s_t+3, ..., finally merged into s_{t+1})
    //   Each merge adds time[i] to time[i+1], propagating to the right.
    //   Final time at s_{t+1} (for the segment FROM s_{t+1}) = sum of time[s_t+1 .. s_{t+1}]
    //
    // But the SEGMENT FROM s_t TO s_{t+1} costs: (position[s_{t+1}] - position[s_t]) * time[s_t]
    //   (the rate at s_t is unchanged since s_t is kept and no merges happen before it within this segment)
    //
    // Wait, but after all merges, the segment FROM s_t uses rate time[s_t] (not accumulated).
    // And the route from s_t to s_{t+1} travels (pos[s_{t+1}]-pos[s_t]) km at rate time[s_t].
    //
    // Hmm, but the NEXT segment after s_{t+1}: rate = accumulated_time_at_s_{t+1} = sum(time[s_t+1..=s_{t+1}])
    //
    // So cost of segment from s_t to s_{t+1} = (pos[s_{t+1}]-pos[s_t]) * time[s_t],
    // BUT the accumulated time at s_{t+1} ALSO affects the NEXT segment.
    //
    // This means the "time" at a given kept sign depends on ALL the merges before it!
    // Specifically, time at kept sign s_{t+1} after all merges =
    //   original time[s_{t+1}] + sum_of_all_merged_times_that_flowed_into_s_{t+1}
    //   = sum(time[s_t+1 .. s_{t+1}])
    //   (only the signs between s_t and s_{t+1} get merged into s_{t+1})
    //
    // And this affects the NEXT NEXT segment (from s_{t+1} to s_{t+2}):
    //   cost = (pos[s_{t+2}] - pos[s_{t+1}]) * effective_time_at_s_{t+1}
    //   = (pos[s_{t+2}] - pos[s_{t+1}]) * sum(time[s_t+1 .. s_{t+1}])
    //
    // Wait, but then the time at s_{t+1} that flows to the NEXT segment is sum(time[s_t+1..=s_{t+1}]).
    // And then more signs might be merged into s_{t+2}, which adds to the accumulated time there.
    //
    // Actually re-examining: time at s_{t+1} after ALL merges from the whole problem:
    // = sum(time[s_t+1 .. s_{t+1}]) because only the consecutive block s_t+1...s_{t+1}-1 merge
    //   into s_{t+1}. This is determined by the kept set.
    //
    // The cost of the segment from s_{t+1} to s_{t+2} is:
    // (pos[s_{t+2}]-pos[s_{t+1}]) * effective_time_at_s_{t+1}
    // = (pos[s_{t+2}]-pos[s_{t+1}]) * sum(time[s_t+1 .. s_{t+1}])
    //
    // So total cost = sum_{block} (pos[s_{t+1}]-pos[s_t]) * time_used_for_this_block
    // where time_used_for_block_t_to_(t+1) = effective_time_at_s_t (which depends on previous block)
    //
    // This means: the effective time at s_t for traveling FROM it =
    //   sum(time[s_{t-1}+1 .. s_t])
    //
    // And segment from s_t to s_{t+1} costs:
    //   (pos[s_{t+1}]-pos[s_t]) * sum(time[s_{t-1}+1 .. s_t])
    //
    // For t=0 (s_0=0): effective rate = time[0] (sign 0 is never merged into, so unchanged) = sum of time[s_{-1}+1..0] = time[0].
    // Actually for the first segment: the rate at position 0 = time[0]. This is (pos[s_1]-pos[0])*time[0].
    // For s_1 to s_2: rate at s_1 = time[s_0+1..=s_1] = time[1..=s_1] if s_0=0.
    //   = sum(time[1..=s_1]).
    // This matches!
    //
    // So: cost = sum_{t=0}^{m-2} (pos[s_{t+1}]-pos[s_t]) * sum(time[s_t-1+1 .. s_t])
    //   where s_{-1} = -1 conceptually, and sum(time[-1+1..s_0]) = sum(time[0..0]) = time[0].
    //
    // Let's redefine: Define prefix_time[i][j] (or use prefix sums).
    // Let ptime[i] = sum(time[0..=i]) (prefix sum of time).
    // Then sum(time[a..=b]) = ptime[b] - ptime[a-1] (with ptime[-1]=0).
    //
    // DP: dp[i][j] = min cost when last kept sign is i, having made j merges among the
    //   signs BETWEEN the start and i (excluding j=merges used so far).
    //
    // dp[i][j] = min over p (previous kept) of:
    //   dp[p][j - (i-p-1)] + (pos[i]-pos[p]) * (ptime[i-1] - ptime[p-1])
    //   where (i-p-1) = merges used between p and i
    //   and the rate at p (for the segment p->i) = sum(time[prev_to_p+1..p]) which was computed earlier.
    //
    // Wait, I'm confusing myself. Let me re-read:
    // cost of segment from s_t to s_{t+1} = (pos[s_{t+1}]-pos[s_t]) * sum(time[s_{t-1}+1..=s_t])
    // This uses s_{t-1} (the sign before s_t in the kept sequence).
    //
    // So the segment cost depends on the previous kept sign, not just the current one.
    // This makes the DP more complex: dp[s_t][j] needs to also encode the previous sign or
    // equivalently encode the "current effective time" at s_t.
    //
    // Alternatively: track the sign BEFORE the current in the transition.
    // dp[prev][cur][j] = min cost for path ending at sign cur, where prev is the previous kept sign, j merges used.
    // But O(n^2 * k) states, n=50, k=10 -> 50*50*10 = 25000. Transitions O(n). Feasible.
    //
    // But we can simplify: dp[cur][j] also implicitly captures influence of prev because:
    // cost of segment from prev to cur = (pos[cur]-pos[prev]) * sum(time[prev_prev+1..=prev])
    // And sum(time[prev_prev+1..=prev]) is determined by dp[prev][...] computation.
    //
    // Actually, let's define things differently:
    // dp[i][j] = min cost to travel from 0 to position[i] having chosen to keep sign i as last,
    //   using exactly j merges total in [1..i-1] (internal signs before i).
    // The cost of the LAST segment (from p to i) uses the effective rate at p.
    // But the effective rate at p depends on the sign before p!
    //
    // So dp[i][j] doesn't capture enough. We need dp[i][j] = min cost where we also know
    // the effective rate at i for the NEXT segment.
    //
    // Alternative decomposition:
    // dp[i][j] = min cost to travel from 0 to position[i], with j merges in [1..i-1],
    //   where the cost of reaching i includes ALL segments up to (but NOT including) the
    //   rate that will be used by the NEXT segment starting at i.
    //
    // At sign i, the rate for the NEXT segment = sum(time[p+1..=i]) where p is the previous kept sign.
    // This depends on p, not just i.
    //
    // OK let me just do dp[p][i][j] where:
    // dp[p][i][j] = min cost to travel from p to i as a single segment (segment p->i),
    //   represented as f(prev=p, cur=i, merges_used_between_p_and_i = i-p-1)
    // Then total: dp[final_sign = n-1][j_total] using chain.
    //
    // Let me redefine cleanly:
    // dp[i][j] = minimum total travel cost from sign 0 to sign i, using exactly j merges among
    //   signs [1..i-1], where the effective time stored at i (for next segment) = acc_i,
    //   and acc_i = sum(time[prev_of_i + 1 .. i]).
    //
    // But acc_i varies with prev_of_i, so we'd need to track it separately.
    //
    // Simplest approach: dp[i][j][acc] but acc is too large.
    //
    // OR: notice that the cost of segment p->i is:
    //   (pos[i] - pos[p]) * acc_p = (pos[i] - pos[p]) * sum(time[pp+1..=p])
    //   And acc_i = sum(time[p+1..=i])
    //
    // The transition adds BOTH the cost of segment p->i AND the info needed for the next segment.
    // We need to know acc_p to compute this cost. So state must include acc_p.
    //
    // Since n<=50, time[i]<=100, k<=10:
    //   acc_p = sum(time[pp+1..=p]) means sum of a subarray of time, max = n*100 = 5000.
    //   States: O(n * k * 5000) = 50*10*5000 = 2.5M - manageable.
    //
    // OR: include acc in the DP state by tracking (last_kept_sign, merges_used, acc_at_last_kept).
    //
    // Even simpler: just do the simulation with (prev_sign, cur_sign, merges) DP.
    // When we move from cur to next:
    //   cost += (pos[next]-pos[cur]) * acc_cur
    //   where acc_cur = sum(time[prev+1..=cur])
    //   acc_next = sum(time[cur+1..=next])
    // So we can store dp[cur][j] = map from acc_cur to min_cost. But acc varies.
    //
    // Just use: dp[cur][j] but parameterize on acc:
    //   For each (cur, j), min cost over all possible acc values.
    //   But diff cur/acc combos may have different future costs.
    //   Actually: dp[cur][j][acc] = min travel cost up to sign cur with j merges and acc = acc at cur.
    //
    // Since acc is determined by (prev, cur), and prev is implicitly available, let's do:
    //   dp[i][j] = min cost of traveling from 0 to i, using j merges, where we keep sign i
    //   and the rate FROM i for the next segment is known.
    // But rate from i = sum(time[prev_i+1..=i]) and we need prev_i for this.
    //
    // Easier: DP with state (last_sign, j) and track prev_sign by having 3D DP:
    //   state (prev, cur, j) but transitions go to (cur, next, j + #merges_skipped).
    // This is O(n^3 * k) = 50^3*10 = 1.25M states, O(n) transitions = 62.5M operations.
    // For n=50, k=10 that's fine.
    //
    // But actually we can do O(n^2 * k) with the insight:
    //   dp[cur][j] = min cost, where the "cost" includes all segments up to cur,
    //   AND we note that the rate at cur is uniquely determined by the choice of prev_cur.
    //   
    //   When transitioning from (prev, cur) to (cur, next):
    //   new_cost = dp_prev_cur_cost + (pos[next]-pos[cur]) * sum(time[prev+1..=cur]) + ...
    //   Hmm, the cost from cur to next also uses acc_cur, which depends on prev.
    //
    // Let me just track (prev_sign, j):
    // Wait, I want dp[i][j] = min cost to travel from sign 0 to sign i.
    // When transitioning: we go from some prev kept sign p at some earlier point to i,
    // and then from i to some next sign.
    // The cost of going from i to next = (pos[next]-pos[i]) * sum(time[p+1..=i])
    // This needs p (the sign before i in the kept sequence).
    //
    // So define dp[i][j] with the constraint that we also record p:
    // dp2[p][i][j] = min cost to travel from 0 to i, last two kept signs are p and i, j merges used.
    //
    // Size: 50*50*10 transitions okay.

    let inf = i64::MAX / 2;
    // ptime[i] = time[0] + ... + time[i] (prefix sum, 0-indexed)
    let ptime: Vec<i64> = {
      let mut p = vec![0i64; n];
      p[0] = time[0] as i64;
      for i in 1..n { p[i] = p[i-1] + time[i] as i64; }
      p
    };

    fn sum_time(ptime: &[i64], a: usize, b: usize) -> i64 {
      // sum of time[a..=b]
      if a == 0 { ptime[b] } else { ptime[b] - ptime[a-1] }
    }

    // dp3[prev][cur][j] = min total cost having traveled from 0 to cur,
    //   where prev is the sign before cur in the kept sequence, j merges used total in [1..cur-1].
    // For the initial segment (0 to first_kept), prev = 0, cur = first_kept.
    // Special case: dp3[0][cur][j] where j = cur-1 merges, cost = (pos[cur]-pos[0]) * time[0].
    let mut dp3 = vec![vec![vec![inf; k + 1]; n]; n];

    // Base: start from sign 0, first kept next sign is cur, merging [1..cur-1]:
    // merges = cur - 1 (we remove signs 1, 2, ..., cur-1)
    // but cur must not be the endpoint removed, and cur can be from 1 to n-1.
    // The segment from 0 to cur: rate = time[0] (sign 0's rate is always time[0])
    // Wait: actually the segment from 0 to cur uses rate at sign 0 = time[0] regardless.
    // Because the merges between 0 and cur don't change time[0].
    // After merging signs 1..=cur-1 into cur, the effective time at sign 0 for its segment = time[0].
    for cur in 1..n {
      let j = cur - 1; // merges used (cur-1 signs between 0 and cur, all merged)
      if j <= k {
        let cost = (position[cur] - position[0]) as i64 * time[0] as i64;
        dp3[0][cur][j] = cost;
      }
    }

    // Transitions: from (prev, cur, j) to (cur, next, j + next-cur-1)
    for prev in 0..n {
      for cur in prev+1..n {
        for j in 0..=k {
          if dp3[prev][cur][j] == inf { continue; }
          let base = dp3[prev][cur][j];
          // rate at cur = sum(time[prev+1..=cur])
          let rate_cur = sum_time(&ptime, prev + 1, cur);
          // choose next sign
          for next in cur+1..n {
            let merges_added = next - cur - 1;
            let new_j = j + merges_added;
            if new_j > k { continue; }
            let seg_cost = (position[next] - position[cur]) as i64 * rate_cur;
            let new_cost = base + seg_cost;
            if new_cost < dp3[cur][next][new_j] {
              dp3[cur][next][new_j] = new_cost;
            }
          }
        }
      }
    }

    // Answer: dp3[prev][n-1][k] for any valid prev
    let mut ans = inf;
    for prev in 0..n-1 {
      if dp3[prev][n-1][k] < ans {
        ans = dp3[prev][n-1][k];
      }
    }
    ans as i32
  }
}