use std::collections::HashMap;
use std::cmp;

impl Solution {
    fn dist(worker: &Vec<i32>, bike: &Vec<i32>) -> usize {
        return ((worker[0] - bike[0]).abs() + (worker[1] - bike[1]).abs()) as usize;
    }

    fn dfs(workers: &mut Vec<Vec<i32>>, bikes: &mut Vec<Vec<i32>>, index: usize, used: usize,
           memo: &mut HashMap<String, usize>) -> usize {
        if index == workers.len() {
            return 0;
        }

        let key = [index.to_string(), String::from("."), used.to_string()].concat();
        if memo.contains_key(&key) {
            return memo.get(&key).unwrap().clone();
        }
        let mut min_dist = std::usize::MAX;
        let mut next_used = used;
        for i in 0..bikes.len() {
            if next_used & (1 << i) != 0 {
                continue;
            }
            next_used = used | (1 << i);
            min_dist = cmp::min(min_dist,
                                Self::dfs(workers, bikes, index + 1, next_used, memo) + Self::dist(&workers[index], &bikes[i]));
            next_used ^= 1 << i;
        }
        memo.insert(key, min_dist);
        return min_dist;
    }

    pub fn assign_bikes(workers: Vec<Vec<i32>>, bikes: Vec<Vec<i32>>) -> i32 {
        let mut memo = HashMap::new();
        let (mut w, mut b) = (workers.clone(), bikes.clone());
        return Self::dfs(&mut w, &mut b, 0, 0, &mut memo) as i32;
    }
}

impl Solution {
    pub fn can_divide_into_subsequences(nums: Vec<i32>, k: i32) -> bool {
        let (mut max, mut cur) = (1, 0);
        for i in 0..nums.len() - 1 {
            if nums[i] == nums[i + 1] {
                cur += 1;
                max = std::cmp::max(max, cur);
            } else {
                cur = 1;
            }
        }

        return nums.len() >= (k * max) as usize;
    }
}

use std::collections::{HashMap, BTreeMap};

struct SnapshotArray {
    map : HashMap<i32, BTreeMap<i32, i32>>,
    version: i32
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl SnapshotArray {

    fn new(length: i32) -> Self {
        SnapshotArray {
            map: HashMap::new(),
            version: 0
        }
    }

    fn set(&mut self, index: i32, val: i32) {
        self.map.entry(index).or_insert(BTreeMap::new());
        self.map.get_mut(&index).unwrap().insert(self.version, val);
    }

    fn snap(&mut self) -> i32 {
        let ret = self.version;
        self.version += 1;
        return ret;
    }

    fn get(&self, index: i32, snap_id: i32) -> i32 {
        if !self.map.contains_key(&index) {
            return 0;
        }
        let vals = self.map.get(&index).unwrap();
        let mut ans = 0;
        for entry in vals {
            if snap_id >= *entry.0 {
                ans = *entry.1;
            } else {
               break;
            }
        }
        return ans;
    }
}