AtCoder Beginner Contest 320 F

https://atcoder.jp/contests/abc320/tasks/abc320_f

0からたどっていけば、座標と残り燃料を状態にして、金額最小を記憶するDPにすればよさそうですが、復路で給油できるかどうかわからないのでどこで給油したのか記憶しなければいけません。しかし、そうすると記憶容量が爆発してしまいます。
代わりに、往路と復路を同時に0から辿るようにします。そうすれば、各ガソリンスタンドで往路で給油するか復路で給油するかいずれも給油しないかの3通りになります。その際、復路は0にたどり着く最小の車の燃料の量を使います。すなわち、往路の燃料と復路の燃料と今いる位置の3つが状態になります。そして、折り返し点の前のガソリンスタンドで折り返して戻ってこられる燃料の差の状態の中から最小のコストを選びます。
Rustのコードしては、最後の部分が難しかったです。結局、indexのタプルをIteratorを使うとうまくいきました。

// Fuel Round Trip
#![allow(non_snake_case)]

use std::cmp::{min, max};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// GasStation ////////////////////

struct GasStation {
    pos: usize,
    price: usize,
    fuel: usize
}

impl GasStation {
    fn read(pos: usize) -> GasStation {
        let v = read_vec();
        let price = v[0];
        let fuel = v[1];
        GasStation { pos, price, fuel }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, usize, Vec<usize>, Vec<GasStation>) {
    let v = read_vec();
    let N: usize = v[0];
    let H: usize = v[1];
    let points: Vec<usize> = read_vec();
    let gas_stations: Vec<GasStation> = (0..N-1).
                                        map(|i| GasStation::read(points[i])).
                                                                    collect();
    (N, H, points, gas_stations)
}

const INF: usize = 10usize.pow(9);

fn initialize_dp(H: usize) -> Vec<Vec<usize>> {
    // 左のindex: 帰りの必要燃料
    // 右のindex: 行きの燃料
    // 値: 最小の金額
    let mut dp = vec![vec![INF; H+1]; H+1];
    dp[0][H] = 0;
    dp
}

fn update_dp(dp: Vec<Vec<usize>>, GS: &GasStation,
                            d: usize, H: usize) -> Vec<Vec<usize>> {
    let mut new_dp = vec![vec![INF; H+1]; H+1];
    for (coming, v) in dp.into_iter().enumerate() {
        if coming + d > H {
            continue
        }
        for (going, price) in v.into_iter().enumerate() {
            if going < d || price == INF {
                continue
            }
            // 帰りに給油
            let c1 = max(coming + d, GS.fuel) - GS.fuel;
            let g2 = going - d;
            new_dp[c1][g2] = min(price+GS.price, new_dp[c1][g2]);
            
            // 行きに給油
            let c2 = coming + d;
            let g1 = min(H, going - d + GS.fuel);
            new_dp[c2][g1] = min(price+GS.price, new_dp[c2][g1]);
            
            // 給油しない
            new_dp[c2][g2] = min(price, new_dp[c2][g2])
        }
    }
    new_dp
}

fn DP(N: usize, H: usize, GSs: Vec<GasStation>) -> Vec<Vec<usize>> {
    let mut dp = initialize_dp(H);
    for i in 0..N-1 {
        let d = if i == 0 { GSs[0].pos } else { GSs[i].pos - GSs[i-1].pos };
        dp = update_dp(dp, &GSs[i], d, H)
    }
    dp
}

fn point(n: usize, points: &Vec<usize>) -> usize {
    if n == 2 && points.len() == 1 {
        0
    }
    else {
        points[points.len()-n]
    }
}

fn F(N: usize, H: usize, points: Vec<usize>,
                        GSs: Vec<GasStation>) -> i64 {
    let last_d = point(1, &points) - point(2, &points);
    if last_d > H {
        return -1
    }
    
    let dp = DP(N, H, GSs);
    let p = (0..H+1-last_d*2).
            flat_map(|c| (c+last_d*2..H+1).map(move |g| (c, g))).
            map(|(c, g)| dp[c][g]).
            min().unwrap();
    if p == INF { -1 } else { p as i64 }
}

fn main() {
    let (N, H, points, gas_stations) = read_input();
    println!("{}", F(N, H, points, gas_stations))
}