Equilateral numbers

use std::str::FromStr;
use std::fmt::Debug;

fn read<T: FromStr>() -> Vec<T>where <T as FromStr>::Err: Debug  {
    let stdin = std::io::stdin();
    let line = stdin.lines().next().unwrap().unwrap();
    line.split_whitespace().map(T::from_str).map(|x| x.unwrap()).collect()
}

fn main() {
    let n = read::<usize>()[0];

    let nums = (1..=1_501_000).map(|n| n * (n + 1) / 2).collect::<Vec<_>>();
    let mut r = vec![0; 1_501_000];
    
    r[1] = 1;

    for i in 2..1_501_000 {
        r[i] = 1 + nums.iter().take_while(|s| i >= **s).map(|s| r[i - s]).min().unwrap();
    }

    println!("{}",
        1 + nums.iter().filter_map(|s| r.get(n.wrapping_sub(*s))).min().unwrap()
    )

}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED