#500604 (Rust) No.1015 おつりは要らないです

提出ソース

結果

問題	No.1015 おつりは要らないです
ユーザー	yoshig0731
提出日時	2020-06-21 01:12:31
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	59 ms / 2,000 ms
コード長	23,976 bytes
コンパイル時間	16,121 ms
コンパイル使用メモリ	380,164 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-04-29 06:16:30
合計ジャッジ時間	16,932 ms
ジャッジサーバーID （参考情報）	judge4 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	55 ms 5,376 KB
testcase_11	AC	58 ms 5,376 KB
testcase_12	AC	52 ms 5,376 KB
testcase_13	AC	55 ms 5,376 KB
testcase_14	AC	59 ms 5,376 KB
testcase_15	AC	52 ms 5,376 KB
testcase_16	AC	53 ms 5,376 KB
testcase_17	AC	54 ms 5,376 KB
testcase_18	AC	53 ms 5,376 KB
testcase_19	AC	52 ms 5,376 KB
testcase_20	AC	49 ms 5,376 KB
testcase_21	AC	50 ms 5,376 KB
testcase_22	AC	52 ms 5,376 KB
testcase_23	AC	48 ms 5,376 KB
testcase_24	AC	53 ms 5,376 KB
testcase_25	AC	48 ms 5,376 KB
testcase_26	AC	50 ms 5,376 KB
testcase_27	AC	47 ms 5,376 KB
testcase_28	AC	49 ms 5,376 KB
testcase_29	AC	50 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	49 ms 5,376 KB
testcase_32	AC	50 ms 5,376 KB
testcase_33	AC	42 ms 5,376 KB
testcase_34	AC	1 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused import: `self::matrix::Matrix`
 --> src/main.rs:2:5
  |
2 | use self::matrix::Matrix;
  |     ^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `self::mod_int::ModInt`
 --> src/main.rs:3:5
  |
3 | use self::mod_int::ModInt;
  |     ^^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::f64::consts::PI`
 --> src/main.rs:6:5
  |
6 | use std::f64::consts::PI;
  |     ^^^^^^^^^^^^^^^^^^^^

warning: unused import: `std::str::*`
 --> src/main.rs:8:5
  |
8 | use std::str::*;
  |     ^^^^^^^^^^^

warning: unused macro definition: `min`
  --> src/main.rs:65:14
   |
65 | macro_rules! min {
   |              ^^^
   |
   = note: `#[warn(unused_macros)]` on by default

warning: unused macro definition: `chmin`
  --> src/main.rs:77:14
   |
77 | macro_rules! chmin {
   |              ^^^^^

warning: unused macro definition: `max`
  --> src/main.rs:89:14
   |
89 | macro_rules! max {
   |              ^^^

warning: unused macro definition: `chmax`
   --> src/main.rs:101:14
    |
101 | macro_rules! chmax {
    |              ^^^^^

warning: the item `Write` is imported redundantly
   --> src/main.rs:136:13
    |
7   | use std::io::*;
    |     ---------- the item `Write` is already imported here
...
136 |         use std::io::Write;
    |             ^^^^^^^^^^^^^^

warning: the item `Read` is imported redundantly
   --> src/main.rs:141:13
    |
7   | use std::io::*;
    |     ---------- the item `Read` is already imported here
...
141 |         use std::io::Read;
    |             ^^^^^^^^^^^^^

warning: the item `BinaryHeap` is imported redundantly
   --> src/main.rs:267:9
    |
5   | use std::collections::*;
    |     ------------------- the item `BinaryHeap` is already imported here
...
267 |     use std::collections::BinaryHeap;
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: unused variable: `tar`
   --> src/main.rs:521:23
    |
521 |         fn act(&self, tar: &Self::T, x: usize) -> Self::T {
    |

ソースコード

raw source code

use self::algebra::*;
use self::matrix::Matrix;
use self::mod_int::ModInt;
use std::cmp::*;
use std::collections::*;
use std::f64::consts::PI;
use std::io::*;
use std::str::*;
use std::string::*;

macro_rules! read {
    (($($t:tt),*)) => {
        ( $(read!($t)),* )
    };
    ([[$t:tt; $len1:expr]; $len2:expr]) => {
        (0..$len2).map(|_| read!([$t; $len1])).collect::<Vec<_>>()
    };

    ([$t:tt; $len:expr]) => {
        (0..$len).map(|_| read!($t)).collect::<Vec<_>>()
    };

    (chars) => {
        read!(String).chars().collect::<Vec<char>>()
    };

    (usize1) => {
        read!(usize) - 1
    };

    ($t:ty) => {{
        let stdin = stdin();
        let stdin = stdin.lock();
        let token: String = stdin
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        token.parse::<$t>().unwrap()
    }};
}

macro_rules! input {
    (mut $name:ident: $t:tt, $($r:tt)*) => {
        let mut $name = read!($t);
        input!($($r)*);
    };

    (mut $name:ident: $t:tt) => {
        let mut $name = read!($t);
    };

    ($name:ident: $t:tt, $($r:tt)*) => {
        let $name = read!($t);
        input!($($r)*);
    };

    ($name:ident: $t:tt) => {
        let $name = read!($t);
    };
}

macro_rules! min {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::min($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::min($a, min!($($rest),+))
    }};
}

macro_rules! chmin {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_min = min!($($cmps),+);
        if $base > cmp_min {
            $base = cmp_min;
            true
        } else {
            false
        }
    }};
}

macro_rules! max {
    ($a:expr $(,)*) => {{
        $a
    }};
    ($a:expr, $b:expr $(,)*) => {{
        std::cmp::max($a, $b)
    }};
    ($a:expr, $($rest:expr),+ $(,)*) => {{
        std::cmp::max($a, max!($($rest),+))
    }};
}

macro_rules! chmax {
    ($base:expr, $($cmps:expr),+ $(,)*) => {{
        let cmp_max = max!($($cmps),+);
        if $base < cmp_max {
            $base = cmp_max;
            true
        } else {
            false
        }
    }};
}

#[derive(Eq, PartialEq, Clone, Debug)]
pub struct Rev<T>(pub T);

impl<T: PartialOrd> PartialOrd for Rev<T> {
    fn partial_cmp(&self, other: &Rev<T>) -> Option<std::cmp::Ordering> {
        other.0.partial_cmp(&self.0)
    }
}

impl<T: Ord> Ord for Rev<T> {
    fn cmp(&self, other: &Rev<T>) -> std::cmp::Ordering {
        other.0.cmp(&self.0)
    }
}

struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        IO(r, std::io::BufWriter::new(w))
    }

    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.to_string().as_bytes()).unwrap();
    }

    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let s: String = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();

        return s.parse::<T>().ok().unwrap();
    }

    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

fn prime_factorization(n: i64) -> HashMap<i64, i64> {
    let mut n = n;
    let mut res = HashMap::new();
    let mut i = 2;
    while i * i <= n {
        while n % i == 0 {
            n /= i;
            let count = res.entry(i).or_insert(0);
            *count += 1;
        }
        i += 1;
    }

    if n > 1 {
        res.insert(n, 1);
    }

    return res;
}

//
// struct Combination {
//     MOD: i64,
//     fac: Vec<i64>,
//     fac_inv: Vec<i64>,
// }
//
// impl Combination {
//     pub fn new(n: i64) -> Self {
//         let MOD: i64 = 1_000_000_007;
//         let mut fac: Vec<i64> = vec![0; n as usize + 1];
//         let mut fac_inv: Vec<i64> = vec![0; n as usize + 1];
//
//         let get_inverse = |mut n: i64| -> i64 {
//             let (mut res, mut p) = (1, MOD - 2);
//
//             while p != 0 {
//                 if p & 1 == 1 {
//                     res = (res * n) % MOD;
//                 }
//                 n = (n * n) % MOD;
//                 p >>= 1;
//             }
//
//             return res;
//         };
//
//         fac[0] = 1;
//
//         for i in 1..n + 1 {
//             fac[i as usize] = (fac[i as usize - 1] * i) % MOD;
//         }
//
//         for i in 0..n + 1 {
//             fac_inv[i as usize] = get_inverse(fac[i as usize]);
//         }
//
//         Combination {
//             MOD: MOD,
//             fac: fac,
//             fac_inv: fac_inv,
//         }
//     }
//
//     fn nCr(&self, n: i64, r: i64) -> i64 {
//         if n < r {
//             return 0;
//         }
//
//         let a: i64 = self.fac[n as usize];
//         let b: i64 = self.fac_inv[(n - r) as usize];
//         let c: i64 = self.fac_inv[r as usize];
//         let bc: i64 = (b * c) % self.MOD;
//
//         return (a * bc) % self.MOD;
//     }
//
//     fn nPr(&self, n: i64, r: i64) -> i64 {
//         if n < r {
//             return 0;
//         }
//
//         let a: i64 = self.fac[n as usize];
//         let b: i64 = self.fac_inv[(n - r) as usize];
//
//         return (a * b) % self.MOD;
//     }
//
//     fn nHr(&self, n: i64, r: i64) -> i64 {
//         if n == 0 && r == 0 {
//             return 1;
//         }
//
//         return self.nCr(n + r - 1, r);
//     }
// }

#[derive(Copy, Clone, Eq, PartialEq)]
struct Edge {
    to: usize,
    cost: i64,
}

fn dijkstra(graph: &Vec<Vec<Edge>>, s: &usize) -> Vec<i64> {
    use std::collections::BinaryHeap;
    let mut dist = vec![1e18 as i64; graph.len()];
    let mut heap = BinaryHeap::new();
    dist[*s] = 0;
    heap.push(Rev((0, *s)));
    while let Some(Rev((cost, v))) = heap.pop() {
        if dist[v] < cost {
            continue;
        }

        for e in &graph[v] {
            if dist[e.to] <= dist[v] + e.cost {
                continue;
            }
            dist[e.to] = dist[v] + e.cost;
            heap.push(Rev((dist[e.to], e.to)));
        }
    }
    return dist;
}

struct LCA {
    par: Vec<Vec<Option<usize>>>,
    dist: Vec<i64>,
}

impl LCA {
    pub fn new(graph: &Vec<Vec<usize>>, root: usize) -> LCA {
        let V = graph.len();
        let mut K = 1;

        while (1 << K) < V {
            K += 1;
        }

        let mut par = vec![vec![None; V]; K];
        let mut dist = vec![-1; V];
        let graph = graph.to_vec();

        fn dfs(
            v: usize,
            p: Option<usize>,
            d: i64,
            graph: &Vec<Vec<usize>>,
            par: &mut Vec<Vec<Option<usize>>>,
            dist: &mut Vec<i64>,
        ) {
            par[0][v] = p;
            dist[v] = d;
            for &to in &graph[v] {
                match p {
                    Some(p) => {
                        if to != p {
                            dfs(to, Some(v), d + 1, graph, par, dist)
                        }
                    }
                    None => dfs(to, Some(v), d + 1, graph, par, dist),
                }
            }
        }

        dfs(root, None, 0, &graph, &mut par, &mut dist);

        for k in 0..K - 1 {
            for v in 0..V {
                match par[k][v] {
                    Some(x) => par[k + 1][v] = par[k][x],
                    None => (),
                }
            }
        }

        LCA {
            par: par,
            dist: dist,
        }
    }

    pub fn query(&self, u: usize, v: usize) -> usize {
        let mut u = u;
        let mut v = v;
        if self.dist[u] < self.dist[v] {
            return self.query(v, u);
        }

        let K = self.par.len();
        for k in 0..K {
            if ((self.dist[u] - self.dist[v]) >> k & 1) == 1 {
                u = self.par[k][u].unwrap();
            }
        }

        if u == v {
            return u;
        }

        for k in (0..K - 1).rev() {
            if self.par[k][u] != self.par[k][v] {
                u = self.par[k][u].unwrap();
                v = self.par[k][v].unwrap();
            }
        }

        return self.par[0][u].unwrap();
    }
}

struct Doubling {
    N: usize,
    LOG: usize,
    next: Vec<Vec<Option<usize>>>,
}

impl Doubling {
    pub fn new(vec: &Vec<usize>, lim: &usize) -> Doubling {
        let N = vec.len();
        let lim = *lim;
        let mut LOG = 1;
        while (1 << LOG) < 2 * lim {
            LOG += 1;
        }

        let mut next = vec![vec![None; N]; LOG];

        for i in 0..N {
            next[0][i] = Some(vec[i]);
        }

        for k in 0..LOG - 1 {
            for i in 0..N {
                match next[k][i] {
                    Some(x) => next[k + 1][i] = next[k][x],
                    None => (),
                }
            }
        }

        Doubling {
            N: N,
            LOG: LOG,
            next: next,
        }
    }

    pub fn query(&self, i: usize, n: usize) -> usize {
        let mut i = i;
        for k in (0..self.LOG).rev() {
            if (n >> k) & 1 == 1 {
                i = self.next[k][i].unwrap();
            }
        }
        return i;
    }
}

struct UnionFind {
    par: Vec<i32>,
}

impl UnionFind {
    pub fn new(n: usize) -> UnionFind {
        UnionFind { par: vec![-1; n] }
    }

    pub fn root(&mut self, x: usize) -> usize {
        if self.par[x] < 0 {
            return x;
        } else {
            let a = self.par[x] as usize;
            self.par[x] = self.root(a) as i32;
            return self.par[x] as usize;
        }
    }

    pub fn same(&mut self, x: usize, y: usize) -> bool {
        self.root(x) == self.root(y)
    }

    pub fn merge(&mut self, x: usize, y: usize) -> bool {
        let mut x = self.root(x);
        let mut y = self.root(y);
        if x == y {
            return false;
        } else {
            if self.par[x] > self.par[y] {
                std::mem::swap(&mut x, &mut y);
            }
            self.par[x] += self.par[y];
            self.par[y] = x as i32;
            return true;
        }
    }

    pub fn size(&mut self, x: usize) -> i64 {
        let a = self.root(x);
        return -self.par[a] as i64;
    }
}

pub mod algebra {
    pub trait Monoid {
        fn id() -> Self;
        fn op(&self, rhs: &Self) -> Self;
    }

    #[derive(Clone, Debug)]
    pub struct Min(i64);

    #[derive(Clone, Debug)]
    pub struct RangeUpdate(i64);

    #[derive(Clone, Debug)]
    pub struct RangeAdd(i64);

    #[derive(Clone, Debug)]
    pub struct Sum(i64);

    impl Monoid for Sum {
        fn id() -> Self {
            Sum(0)
        }

        fn op(&self, rhs: &Self) -> Self {
            Sum(self.0 + rhs.0)
        }
    }

    impl Monoid for Min {
        fn id() -> Self {
            Min(std::i32::MAX as i64)
        }

        fn op(&self, rhs: &Self) -> Self {
            Min(std::cmp::min(self.0, (*rhs).0))
        }
    }

    pub trait Operator {
        type T;
        fn id() -> Self;
        fn op(&self, rhs: &Self) -> Self;
        fn act(&self, tar: &Self::T, x: usize) -> Self::T;
    }

    impl Operator for RangeUpdate {
        type T = Min;
        fn id() -> Self {
            RangeUpdate(0)
        }

        fn op(&self, rhs: &Self) -> Self {
            (*rhs).clone()
        }

        fn act(&self, tar: &Self::T, x: usize) -> Self::T {
            Min(self.0)
        }
    }

    impl Operator for RangeAdd {
        type T = Sum;
        fn id() -> Self {
            RangeAdd(0)
        }

        fn op(&self, rhs: &Self) -> Self {
            RangeAdd(self.0 + rhs.0)
        }

        // Sum(tar.0 + self.0 * x as i64)
        fn act(&self, tar: &Self::T, x: usize) -> Self::T {
            Sum(tar.0 + self.0 * x as i64)
        }
    }

    pub trait Zero {
        fn zero() -> Self;
    }

    impl Zero for usize {
        fn zero() -> Self {
            0usize
        }
    }

    pub trait One {
        fn one() -> Self;
    }

    impl One for usize {
        fn one() -> Self {
            1usize
        }
    }
}

struct LazySegTree<M: Monoid, O: Operator<T = M>> {
    dat: Vec<M>,
    lzy: Vec<O>,
    need_update: Vec<bool>,
    size: usize,
}

impl<M: Monoid + Clone, O: Operator<T = M> + Clone> LazySegTree<M, O> {
    pub fn new(vec: Vec<M>) -> LazySegTree<M, O> {
        let n = vec.len();
        let mut sz = 1;
        while sz < n {
            sz <<= 1;
        }
        let mut dat = vec![M::id(); sz << 1];
        for i in 0..n {
            dat[i + sz] = vec[i].clone();
        }
        for k in (1..sz).rev() {
            dat[k] = dat[k << 1].op(&dat[(k << 1) + 1]);
        }

        return LazySegTree {
            dat: dat,
            lzy: vec![O::id(); sz << 1],
            need_update: vec![false; sz << 1],
            size: sz,
        };
    }

    pub fn eval(&mut self, l: usize, r: usize, k: usize) {
        if !self.need_update[k] {
            return;
        }
        self.dat[k] = self.lzy[k].act(&self.dat[k], r - l);
        if (k << 1) < self.dat.len() {
            self.lzy[k << 1] = self.lzy[k << 1].op(&self.lzy[k]);
            self.lzy[(k << 1) + 1] = self.lzy[(k << 1) + 1].op(&self.lzy[k]);
            self.need_update[k << 1] = true;
            self.need_update[(k << 1) + 1] = true;
        }
        self.lzy[k] = O::id();
        self.need_update[k] = false;
    }

    pub fn update(&mut self, a: usize, b: usize, x: O) {
        let sz = self.size;
        self._update(a, b, &x, 0, sz, 1);
    }

    pub fn _update(&mut self, a: usize, b: usize, x: &O, l: usize, r: usize, k: usize) {
        self.eval(l, r, k);
        if b <= l || r <= a {
            return;
        } else if a <= l && r <= b {
            self.lzy[k] = self.lzy[k].op(x);
            self.need_update[k] = true;
            self.eval(l, r, k);
        } else {
            let mid = (l + r) >> 1;
            self._update(a, b, x, l, mid, k << 1);
            self._update(a, b, x, mid, r, (k << 1) + 1);
            self.dat[k] = self.dat[k << 1].op(&self.dat[(k << 1) + 1]);
        }
    }

    pub fn query(&mut self, a: usize, b: usize) -> M {
        let sz = self.size;
        return self._query(a, b, 0, sz, 1);
    }

    pub fn _query(&mut self, a: usize, b: usize, l: usize, r: usize, k: usize) -> M {
        self.eval(l, r, k);
        if b <= l || r <= a {
            return M::id();
        } else if a <= l && r <= b {
            return self.dat[k].clone();
        } else {
            let mid = (l + r) >> 1;
            let vl = self._query(a, b, l, mid, k << 1);
            let vr = self._query(a, b, mid, r, (k << 1) + 1);
            return vl.op(&vr);
        }
    }
}

struct SegTree<M: Monoid> {
    dat: Vec<M>,
    size: usize,
}

impl<M: Monoid + Clone> SegTree<M> {
    pub fn new(n: usize) -> SegTree<M> {
        let mut sz = 1;
        while sz < n {
            sz <<= 1;
        }

        SegTree::<M> {
            dat: vec![M::id(); sz * 2],
            size: sz,
        }
    }

    pub fn update(&mut self, k: usize, val: M) {
        let mut k = k + self.size;
        self.dat[k] = val;
        while k > 0 {
            k = k >> 1;
            self.dat[k] = self.dat[k << 1].op(&self.dat[(k << 1) + 1]);
        }
    }

    pub fn query(&self, a: usize, b: usize) -> M {
        let mut lx = M::id();
        let mut rx = M::id();
        let mut l = a + self.size;
        let mut r = b + self.size;
        while l < r {
            if (l & 1) == 1 {
                lx = lx.op(&self.dat[l]);
                l += 1;
            }

            if (r & 1) == 1 {
                r -= 1;
                rx = self.dat[r].op(&rx);
            }

            l >>= 1;
            r >>= 1;
        }

        return lx.op(&rx);
    }
}

fn decode(v: Vec<char>) -> Vec<(char, usize)> {
    let mut res = Vec::new();
    let mut now = v[0];
    let mut cnt = 1;

    for i in 1..v.len() {
        if v[i] == now {
            cnt += 1;
        } else {
            res.push((now, cnt));
            cnt = 1;
            now = v[i];
        }
    }
    res.push((now, cnt));

    return res;
}

pub mod mod_int {
    use super::algebra::{One, Zero};
    use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};

    type Num = usize;

    const MOD: usize = 1e9 as usize + 7;

    #[derive(Clone, Copy)]
    pub struct ModInt<T: Copy + Clone>(pub T);

    impl Add<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self + rhs.0
        }
    }

    impl Add<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn add(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            let mut t = rhs + self.0;
            if t >= MOD {
                t = t - MOD;
            }
            ModInt(t)
        }
    }

    impl Sub<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: Num) -> ModInt<Num> {
            let rhs = if rhs >= MOD { rhs % MOD } else { rhs };
            let value = if self.0 < rhs { self.0 + MOD } else { self.0 };
            ModInt(value - rhs)
        }
    }

    impl Sub<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self - rhs.0
        }
    }

    impl AddAssign<Num> for ModInt<Num> {
        fn add_assign(&mut self, other: Num) {
            *self = *self + other;
        }
    }

    impl AddAssign<ModInt<Num>> for ModInt<Num> {
        fn add_assign(&mut self, other: ModInt<Num>) {
            *self = *self + other;
        }
    }

    impl SubAssign<Num> for ModInt<Num> {
        fn sub_assign(&mut self, other: Num) {
            *self = *self - other;
        }
    }

    impl SubAssign<ModInt<Num>> for ModInt<Num> {
        fn sub_assign(&mut self, other: ModInt<Num>) {
            *self = *self - other;
        }
    }

    impl Div<Num> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            self * ModInt(rhs).pow(MOD - 2)
        }
    }

    impl Div<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;
        fn div(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self / rhs.0
        }
    }

    impl DivAssign<Num> for ModInt<Num> {
        fn div_assign(&mut self, rhs: Num) {
            *self = *self / rhs
        }
    }

    impl DivAssign<ModInt<Num>> for ModInt<Num> {
        fn div_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self / rhs
        }
    }

    impl Mul<ModInt<Num>> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> {
            self * rhs.0
        }
    }

    impl Mul<Num> for ModInt<Num> {
        type Output = ModInt<Num>;

        fn mul(self, mut rhs: Num) -> ModInt<Num> {
            if rhs >= MOD {
                rhs %= MOD;
            }
            let t = (self.0 * rhs) % MOD;
            ModInt(t)
        }
    }

    impl MulAssign<Num> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: Num) {
            *self = *self * rhs;
        }
    }

    impl MulAssign<ModInt<Num>> for ModInt<Num> {
        fn mul_assign(&mut self, rhs: ModInt<Num>) {
            *self = *self * rhs;
        }
    }

    impl ModInt<Num> {
        pub fn pow(self, e: Num) -> ModInt<Num> {
            let mut result = ModInt(1);
            let mut cur = self;
            let mut e = e;
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                }
                e >>= 1;
                cur *= cur;
            }
            result
        }
    }

    impl Zero for ModInt<Num> {
        fn zero() -> Self {
            ModInt(0)
        }
    }

    impl One for ModInt<Num> {
        fn one() -> Self {
            ModInt(1)
        }
    }
}

struct Eratosthenes {
    n: usize,
    prime: Vec<bool>,
}

impl Eratosthenes {
    pub fn new(n: usize) -> Eratosthenes {
        let mut prime = vec![true; n + 1];
        prime[0] = false;
        prime[1] = false;
        let mut i = 2;
        while i * i <= n {
            if prime[i] {
                let mut p = i * 2;
                while p <= n {
                    prime[p] = false;
                    p += i;
                }
            }
            i += 1;
        }

        Eratosthenes { n: n, prime: prime }
    }
}

pub mod matrix {
    use super::algebra::{One, Zero};
    use std::ops::{Add, Mul};

    #[derive(Clone)]
    pub struct Matrix<T: Add + Mul + Clone + Copy + One + Zero>(pub Vec<Vec<T>>);

    impl<T: Add<Output = T> + Mul<Output = T> + Clone + Copy + One + Zero> Matrix<T> {
        pub fn mul(&mut self, rhs: &Matrix<T>) -> Matrix<T> {
            let n = self.0.len();
            let m = rhs.0[0].len();
            let p = self.0[0].len();
            let mut res = vec![vec![T::zero(); m]; n];
            for i in 0..n {
                for j in 0..m {
                    for k in 0..p {
                        res[i][j] = res[i][j] + self.0[i][k] * rhs.0[k][j]
                    }
                }
            }

            return Matrix(res);
        }

        // pub fn update(&mut self) -> Vec<Vec<T>> {
        //     let m = self.mat.len();
        //     let mut res = vec![vec![T::zero(); m]; m];
        //     for i in 0..m {
        //         for j in 0..m {
        //             for k in 0..m {
        //                 res[i][j] = res[i][j] + self.mat[i][k] * self.mat[k][j];
        //             }
        //         }
        //     }
        //     return res;
        // }

        pub fn pow(&mut self, k: usize) -> Matrix<T> {
            let n = self.0.len();
            let mut k = k;
            let mut res = Matrix(vec![vec![T::zero(); n]; n]);
            let mut b = (*self).clone();
            for i in 0..n {
                res.0[i][i] = T::one();
            }

            while k > 0 {
                if k & 1 == 1 {
                    res = b.mul(&res);
                }
                b = b.mul(&b.clone());
                k >>= 1;
            }

            return res;
        }
    }
}

#[derive(Clone, Copy)]
struct Alpha(i64);

impl Monoid for Alpha {
    fn id() -> Self {
        Alpha(0i64)
    }

    fn op(&self, rhs: &Self) -> Self {
        Alpha(self.0 | rhs.0)
    }
}

fn solve() {
    input! {
        n: usize,
        x: i64,
        y: i64,
        z: i64,
        a: [i64; n]
    }

    let mut heap: BinaryHeap<i64> = a.into_iter().map(|x| x + 1).collect();
    let mut yens = vec![10000i64, 5000, 1000];
    let mut cnts = vec![z, y, x];

    for v in 0..3 {
        let yen = yens[v];
        let mut cnt = cnts[v];

        for i in 0..n {
            let x = heap.pop().unwrap();
            let us = min(x / yen, cnt);
            cnt -= us;
            heap.push(x - us * yen);
        }

        for i in 0..n {
            let mut x = heap.pop().unwrap();
            if cnt > 0 {
                cnt -= 1;
                x = 0;
            }
            heap.push(x);
        }
    }

    println!(
        "{}",
        if heap.iter().map(|&x| x).sum::<i64>() <= 0i64 {
            "Yes"
        } else {
            "No"
        }
    );
}

fn main() {
    solve();
    // input! {
    //     t: usize
    // }
    //
    // for _ in 0..t {
    //     solve();
    // }
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード