提出 #73588785

---

ソースコード 拡げる

pub mod lib {
    lazy_static! {
        pub static ref SEMVER: Regex = Regex::new(r#""#).expect("error parsing regex");
    }

    pub use external_lib::*;
    pub use my_lib::*;

    pub mod external_lib {
        pub use ac_library::{
            FenwickTree, LazySegtree, MapMonoid, MfGraph, ModInt as Mint, Monoid, Segtree,
        };
        pub use itertools::{Itertools, chain};
        pub use lazy_static::lazy_static;
        pub use memoise::*;
        pub use multimap::MultiMap;
        pub use num::{
            BigInt,
            integer::{ExtendedGcd, Integer, gcd},
        };
        pub use ordered_float::NotNan;
        pub use petgraph::unionfind::UnionFind;
        pub use proconio::{
            fastout, input,
            marker::{Bytes, Chars, Isize1, Usize1},
        };
        pub use regex::Regex;
        pub use std::{
            cmp::{Reverse, max, min},
            collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque},
            f64::consts::PI,
            iter::{empty, from_fn, once, repeat, repeat_n, repeat_with, successors, zip},
            mem::{swap, take},
        };
        pub use superslice::Ext;
    }
    pub mod my_lib {
        pub use combinations::*;
        pub use helpful::*;
        pub use macros::*;
        pub use setup::*;
        pub use vec2::*;

        pub mod combinations {
            #[inline]
            pub fn factorial(n: usize) -> usize {
                (1..=n).product::<usize>()
            }
            #[inline]
            pub fn permutation(n: usize, r: usize) -> usize {
                if n < r {
                    0
                } else {
                    (n - r + 1..=n).product::<usize>()
                }
            }
            /// これを何度も使いたい時は階乗を前計算するようなプログラムを作ることを推奨
            #[inline]
            pub fn combination(n: usize, r: usize) -> usize {
                if n < r {
                    0
                } else {
                    permutation(n, r) / factorial(r)
                }
            }
            #[inline]
            pub fn homogeneous(n: usize, r: usize) -> usize {
                combination(n + r - 1, r)
            }
        }
        pub mod helpful {
            use std::{iter::from_fn, ops::DivAssign};

            use easy_ext::ext;
            use num::Integer;

            #[ext(VecCharToString)]
            pub impl<'a, T: 'a> Vec<T>
            where
                String: FromIterator<&'a T>,
            {
                fn to_string(&'a self) -> String {
                    self.iter().collect::<String>()
                }
            }

            #[ext(Digits)]
            pub impl<N: Integer + DivAssign + Copy + 'a, 'a> N {
                fn digits(mut self, a: N) -> impl Iterator<Item = N> {
                    from_fn(move || {
                        (!self.is_zero()).then(|| {
                            let t = self % a;
                            self /= a;
                            t
                        })
                    })
                }
            }

            pub fn factorization(mut n: usize) -> Vec<(usize, usize)> {
                let mut v = vec![];
                for c in 2..=n.isqrt() {
                    let mut i = 0;
                    while n % c == 0 {
                        n /= c;
                        i += 1;
                    }
                    if i != 0 {
                        v.push((c, i));
                    }
                    if n == 1 {
                        return v;
                    }
                }
                if n != 1 {
                    v.push((n, 1));
                }
                v
            }
        }
        pub mod macros {
            use std::{borrow::Cow, collections::VecDeque, fmt::Display};

            use ac_library::ModInt;
            use itertools::{Format, Itertools};

            pub trait AtcoderOutput {
                fn ac_output(&'_ self) -> Cow<'_, str>;
            }

            impl AtcoderOutput for bool {
                fn ac_output(&'_ self) -> Cow<'_, str> {
                    Cow::Borrowed(if *self { "Yes" } else { "No" })
                }
            }
            impl<T: Display> AtcoderOutput for Option<T> {
                fn ac_output(&'_ self) -> Cow<'_, str> {
                    if let Some(a) = self {
                        Cow::Owned(format!("{a}"))
                    } else {
                        Cow::Borrowed("-1")
                    }
                }
            }
            impl<T: Display, E> AtcoderOutput for Result<T, E> {
                fn ac_output(&'_ self) -> Cow<'_, str> {
                    if let Ok(a) = self {
                        Cow::Owned(format!("{a}"))
                    } else {
                        Cow::Borrowed("-1")
                    }
                }
            }
            impl<T: Display> AtcoderOutput for Vec<T> {
                fn ac_output(&'_ self) -> Cow<'_, str> {
                    Cow::Owned(self.iter().format(" ").to_string())
                }
            }
            impl<T: Display> AtcoderOutput for VecDeque<T> {
                fn ac_output(&'_ self) -> Cow<'_, str> {
                    Cow::Owned(self.iter().format(" ").to_string())
                }
            }
            impl<T> AtcoderOutput for Format<'_, T>
            where
                for<'a> Format<'a, T>: ToString,
            {
                fn ac_output(&'_ self) -> Cow<'_, str> {
                    Cow::Owned(self.to_string())
                }
            }
            macro_rules! ans_impl {
                ($t: ident, $($u: ident),+) => {
                    ans_impl!($t);
                    ans_impl!($($u),+);
                };
                ($t:ident) => {
                    impl AtcoderOutput for $t {
                        fn ac_output(&'_ self) -> Cow<'_, str> {
                            Cow::Owned(format!("{}", self))
                        }
                    }
                }
            }
            ans_impl!(
                u8, i8, u16, i16, u32, i32, u64, i64, u128, i128, usize, isize, f32, f64, String,
                str, char, ModInt
            );

            #[macro_export]
            macro_rules! ans {
                ($v: expr, $($x: expr),+) => {{
                    ans!($v);
                    ans!($($x),+)
                }
                };
                (yes) => {
                    yes!()
                };
                (no) => {
                    no!()
                };
                ($output: expr) => {
                    println!("{}", $output.ac_output())
                };
                () => {{}}
            }

            #[macro_export]
            macro_rules! yes {
                () => {
                    println!("Yes")
                };
            }

            #[macro_export]
            macro_rules! no {
                () => {
                    println!("No")
                };
            }

            #[macro_export]
            macro_rules! chmax {
                ($var: expr; $($x: expr),+) => {{
                    let x = $crate::max!($($x),+);
                    if $var < x {
                        $var = x;
                        true
                    } else {
                        false
                    }
                }};
            }

            #[macro_export]
            macro_rules! chmin {
                ($var: expr; $($x: expr),+) => {{
                    let x = $crate::min!($($x),+);
                    if $var > x {
                        $var = x;
                        true
                    } else {
                        false
                    }
                }};
            }

            #[macro_export]
            macro_rules! max {
                ($($t: expr),+) => {[$($t),+].into_iter().max().unwrap()};
            }

            #[macro_export]
            macro_rules! min {
                ($($t: expr),+) => {[$($t),+].into_iter().min().unwrap()};
            }

            #[macro_export]
            macro_rules! flat_max {
                ($($t: expr),+) => {[$($t),+].into_iter().flatten().max()};
            }

            #[macro_export]
            macro_rules! flat_min {
                ($($t: expr),+) => {[$($t),+].into_iter().flatten().min()};
            }

            #[macro_export]
            macro_rules! range_2d {
                ($tuple: expr) => {
                    range_2d!((0, 0), $tuple)
                };
                ($v: expr, $w: expr) => {
                    ($v.0..$w.0).flat_map(|a| ($v.1..$w.1).map(move |b| (a, b)))
                };
            }

            #[macro_export]
            macro_rules! nest {
                ($identify: expr; $dim1: expr, $($dim2: expr),+) => {
                    nest![nest![$identify; $($dim2),+]; $dim1]
                };
                ($identify: expr; $dim: expr) => {
                    vec![$identify; $dim]
                }
            }
        }
        pub mod setup {
            use std::iter::once;

            /// エラトステネスの篩
            pub fn eratosthenes(end: usize) -> Vec<usize> {
                let mut table = vec![true; end - 1];
                let mut ans = vec![];
                assert!(end > 1);
                for i in 2..=end {
                    if table[i - 2] {
                        for j in i..=end / i {
                            table[j * i - 2] = false;
                        }
                        ans.push(i);
                    }
                }
                ans
            }

            /// インテレータを受け取って累積和、\[0\]は区間和の計算用にT::default()
            pub fn cumulative_sum<
                T: std::ops::AddAssign + Default + Copy,
                I: IntoIterator<Item = T>,
            >(
                v: I,
            ) -> Vec<T> {
                once(T::default())
                    .chain(v.into_iter().scan(T::default(), |prev, s| {
                        *prev += s;
                        Some(*prev)
                    }))
                    .collect()
            }

            pub fn build_graph_undirected(
                n: usize,
                v: impl IntoIterator<Item = (usize, usize)>,
            ) -> Vec<Vec<usize>> {
                let mut nv = vec![vec![]; n];
                for (i, j) in v {
                    nv[i].push(j);
                    nv[j].push(i);
                }
                nv
            }

            pub fn build_graph_directed(
                n: usize,
                v: impl IntoIterator<Item = (usize, usize)>,
            ) -> Vec<Vec<usize>> {
                let mut nv = vec![vec![]; n];
                for (i, j) in v {
                    nv[i].push(j);
                }
                nv
            }

            pub fn build_graph_with_cost_undirected<T: Clone>(
                n: usize,
                v: impl IntoIterator<Item = (usize, usize, T)>,
            ) -> Vec<Vec<(usize, T)>> {
                let mut nv = vec![vec![]; n];
                for (i, j, w) in v {
                    nv[i].push((j, w.clone()));
                    nv[j].push((i, w.clone()));
                }
                nv
            }

            pub fn build_graph_with_cost_directed<T: Clone>(
                n: usize,
                v: impl IntoIterator<Item = (usize, usize, T)>,
            ) -> Vec<Vec<(usize, T)>> {
                let mut nv = vec![vec![]; n];
                for (i, j, w) in v {
                    nv[i].push((j, w.clone()));
                }
                nv
            }
        }
        pub mod vec2 {
            use easy_ext::ext;

            use crate::range_2d;

            /// 二次元Vecを時計回りに回転
            #[ext(Rotate)]
            impl<T: Copy> Vec<Vec<T>> {
                pub fn rotate_vec(&self) -> Self {
                    if self.is_empty() {
                        return vec![];
                    }
                    (0..self[0].len())
                        .map(|i| (0..self.len()).map(|j| self[j][i]).collect())
                        .collect()
                }
            }
            /// 二次元Vecを転置
            #[ext(TransposeVec)]
            impl<T: Copy> Vec<Vec<T>> {
                pub fn transpose_vec(&self) -> Self {
                    if self.is_empty() {
                        return vec![];
                    }
                    let n = self[0].len();
                    (0..n)
                        .map(|i| (0..self.len()).map(|j| self[j][i]).collect::<Vec<T>>())
                        .collect()
                }
            }
            /// 評価関数f()で有効範囲のみを残す
            #[ext(TrimBy)]
            impl<T: PartialEq + Copy> Vec<Vec<T>> {
                pub fn trim_by<F: Fn(T) -> bool + Copy>(&self, f: F) -> ((usize, usize), Self) {
                    if let Some((upper, _)) = self
                        .iter()
                        .enumerate()
                        .find(|(_, a)| a.iter().any(|a| f(*a)))
                    {
                        let lower = self
                            .iter()
                            .enumerate()
                            .rev()
                            .find(|(_, a)| a.iter().any(|a| f(*a)))
                            .unwrap()
                            .0;
                        let new = self[upper..=lower].to_vec().transpose_vec();
                        let left = new
                            .iter()
                            .enumerate()
                            .find(|(_, a)| a.iter().any(|a| f(*a)))
                            .unwrap()
                            .0;
                        let right = new
                            .iter()
                            .enumerate()
                            .rev()
                            .find(|(_, a)| a.iter().any(|a| f(*a)))
                            .unwrap()
                            .0;
                        ((upper, left), new[left..=right].to_vec().transpose_vec())
                    } else {
                        ((0, 0), vec![vec![]])
                    }
                }
            }

            #[ext(FindAll)]
            impl<T: PartialEq> Vec<Vec<T>> {
                pub fn find_all(&self, p: T) -> impl Iterator<Item = (usize, usize)> {
                    range_2d!((self.len(), self.first().unwrap_or(&vec![]).len()))
                        .filter(move |&v| self[v.0][v.1] == p)
                }
            }
        }
    }
}

use lib::*;

#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        m: usize,
        mut a: [(u8, usize); n]
    }
    let b = a
        .extract_if(.., |a| a.0 == 1)
        .map(|a| a.1)
        .k_largest(m)
        .collect_vec();
    let a = a.into_iter().map(|a| a.1).k_largest(k - m).collect_vec();
    if a.len() == k - m && b.len() == m {
        ans!(b.iter().sum::<usize>() + a.iter().sum::<usize>())
    } else {
        ans!(-1)
    }
}

提出情報

ジャッジ結果