fn f(n: usize) -> u128 {
    static mut CACHE: Option<Vec<u128>> = None;
    unsafe {
        if CACHE.is_none() {
            let mut v = Vec::with_capacity(100000);
            v.push(1);
            v.push(1);
            v.push(2);
            CACHE = Some(v);
        }

        let cache = CACHE.as_mut().unwrap();
        for x in cache.len()..=n {
            let mut ans = *cache.get_unchecked(x - 1);
            ans += cache.get_unchecked(x - 2);
            ans += cache.get_unchecked(x - 3);
            cache.push(ans)
        }
        cache[n]
    }
}

fn main() {
    use std::time::Instant;
    let t = Instant::now();
    let ans = f(100);
    println!("f({}) = {}, time: {:?}", 100, ans, t.elapsed());
}