#804916 (Rust) No.2093 Shio Ramen

• 問題: No.2093 Shio Ramen
• ユーザー: Moss_Local
• 提出日時: 2022-10-07 21:30:37
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 10 ms / 2,000 ms
• コード長: 17,696 bytes
• コンパイル時間: 16,736 ms
• コンパイル使用メモリ: 381,232 KB
• 実行使用メモリ: 9,728 KB
• 最終ジャッジ日時: 2024-06-12 06:14:25
• 合計ジャッジ時間: 16,941 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,820 KB
testcase_01	AC	1 ms; 6,812 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	1 ms; 6,940 KB
testcase_04	AC	1 ms; 6,944 KB
testcase_05	AC	1 ms; 6,944 KB
testcase_06	AC	1 ms; 6,944 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	AC	2 ms; 6,940 KB
testcase_10	AC	7 ms; 7,040 KB
testcase_11	AC	1 ms; 6,944 KB
testcase_12	AC	1 ms; 6,940 KB
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	2 ms; 6,944 KB
testcase_15	AC	5 ms; 6,944 KB
testcase_16	AC	3 ms; 6,944 KB
testcase_17	AC	2 ms; 6,940 KB
testcase_18	AC	9 ms; 9,216 KB
testcase_19	AC	6 ms; 6,940 KB
testcase_20	AC	4 ms; 6,944 KB
testcase_21	AC	4 ms; 6,944 KB
testcase_22	AC	4 ms; 6,940 KB
testcase_23	AC	9 ms; 9,728 KB
testcase_24	AC	9 ms; 9,728 KB
testcase_25	AC	10 ms; 9,600 KB
testcase_26	AC	10 ms; 9,728 KB
testcase_27	AC	10 ms; 9,728 KB
testcase_28	AC	9 ms; 9,600 KB
testcase_29	AC	9 ms; 9,728 KB
testcase_30	AC	9 ms; 9,728 KB

コンパイルメッセージ

warning: unnecessary parentheses around type
  --> src/main.rs:85:15
   |
85 | fn readi() -> (i64) {
   |               ^   ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
85 - fn readi() -> (i64) {
85 + fn readi() -> i64 {
   |

warning: unused variable: `i`
   --> src/main.rs:610:9
    |
610 |     for i in 0..n {
    |         ^ help: if this is intentional, prefix it with an underscore: `_i`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable `X` should have a snake case name
   --> src/main.rs:332:13
    |
332 |         let X = x * (a2 * (b2 + c2 - a2)) + y * (b2 * (c2 + a2 - b2)) + z * (c2 * (a2 + b2 - c2));
    |             ^ help: convert the identifier to snake case (notice the capitalization): `x`
    |
    = note: `#[warn(non_snake_case)]` on by default

warning: variable `Y` should have a snake case name
   --> src/main.rs:333:13
    |
333 |         let Y = a2 * (b2 + c2 - a2) + b2 * (c2 + a2 - b2) + c2 * (a2 + b2 - c2);
    |             ^ help: convert the identifier to snake case (notice the capitalization): `y`

ソースコード

// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use core::num;
use std::any::Any;
use std::cmp::Ordering::*;
use std::collections::btree_map::Values;
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::error::Error;
use std::f32::consts::E;
use std::fmt::Debug;
use std::fmt::Display;
use std::fs::File;
use std::hash::Hash;
use std::io::prelude::*;
use std::io::*;
use std::iter::Filter;
use std::iter::FromIterator;
use std::marker::Copy;
use std::mem::*;
use std::ops::BitAnd;
use std::ops::Bound::*;
use std::ops::RangeBounds;
use std::ops::{Add, Mul, Neg, Sub};
use std::process;
use std::slice::from_raw_parts;
use std::str;
use std::vec;

const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD: i64 = 1000000007;
// const MOD: i64 = 998244353;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
// const MOD: i64 = INF;

use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        println!("{}", $x);
    };
}

macro_rules! d {
    ($x:expr) => {
        println!("{:?}", $x);
    };
}
#[allow(unused_macros)]
pub mod macros {
    macro_rules! min { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); std::cmp::min($x, y) } }}
    macro_rules! max { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); std::cmp::max($x, y) } }}
    macro_rules! chmin { ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); if $x > y { $x = y; true } else { false } }}}
    macro_rules! chmax { ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); if $x < y { $x = y; true } else { false } }}}
    macro_rules! multi_vec { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_vec![$element; ($($lens),*)]; $len] ); ($element: expr; ($len: expr)) => ( vec![$element; $len] ); }
    macro_rules! multi_box_array { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_box_array![$element; ($($lens),*)]; $len].into_boxed_slice() ); ($element: expr; ($len: expr)) => ( vec![$element; $len].into_boxed_slice() ); }
    #[allow(unused_imports)]
    pub(super) use {chmax, chmin, max, min, multi_box_array, multi_vec};
}
fn main() {
    solve();
}

// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn readi() -> (i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    iter.next().unwrap().parse::<i64>().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
    )
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
    )
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
    )
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<f64>().unwrap(),
        iter.next().unwrap().parse::<f64>().unwrap(),
    )
}

fn readcc() -> (char, char) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<char>().unwrap(),
        iter.next().unwrap().parse::<char>().unwrap(),
    )
}

fn readuuu() -> (usize, usize, usize) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
        iter.next().unwrap().parse::<usize>().unwrap(),
    )
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
    let mut str = String::new();
    let _ = stdin().read_line(&mut str).unwrap();
    let mut iter = str.split_whitespace();
    (
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
        iter.next().unwrap().parse::<i64>().unwrap(),
    )
}

use std;

const EPS: f64 = 1e-9;

#[derive(Debug, Clone, Copy)]
#[allow(dead_code)]
pub struct Vector2D(f64, f64);

impl Vector2D {
    pub fn add(a: f64, b: f64) -> f64 {
        let c = a + b;
        if c.abs() < EPS {
            0.0
        } else {
            c
        }
    }
    pub fn dot(self, other: Vector2D) -> f64 {
        Self::add(self.0 * other.0, self.1 * other.1)
    }
    pub fn det(self, other: Vector2D) -> f64 {
        Self::add(self.0 * other.1, -self.1 * other.0)
    }
    pub fn complex_mul(self, other: Vector2D) -> Self {
        let real = self.0 * other.0 - self.1 * other.1;
        let imag = self.0 * other.1 + self.1 * other.0;
        Vector2D(real, imag)
    }
    pub fn dist(self, other: Self) -> f64 {
        (self - other).len()
    }
    pub fn len(&self) -> f64 {
        f64::sqrt((self.0).powi(2) + (self.1).powi(2))
    }
    pub fn unit(self) -> Vector2D {
        let l = self.len();
        Vector2D(self.0 / l, self.1 / l)
    }
    #[doc = "orthogonal vector"]
    pub fn normal(self) -> Vector2D {
        Vector2D(self.1, -self.0).unit()
    }
    #[doc = "bisection of the angle"]
    pub fn bisect(a: Vector2D, b: Vector2D) -> Vector2D {
        (a.unit() + b.unit()).unit()
    }
}

impl std::ops::Add for Vector2D {
    type Output = Vector2D;
    fn add(self, rhs: Vector2D) -> Self::Output {
        Vector2D(Vector2D::add(self.0, rhs.0), Vector2D::add(self.1, rhs.1))
    }
}

impl std::ops::Sub for Vector2D {
    type Output = Vector2D;
    fn sub(self, rhs: Vector2D) -> Self::Output {
        Vector2D(Vector2D::add(self.0, -rhs.0), Vector2D::add(self.1, -rhs.1))
    }
}

impl std::ops::Mul<f64> for Vector2D {
    type Output = Vector2D;
    fn mul(self, rhs: f64) -> Self::Output {
        Vector2D(rhs * self.0, rhs * self.1)
    }
}

impl std::ops::Div<f64> for Vector2D {
    type Output = Vector2D;
    fn div(self, rhs: f64) -> Self::Output {
        Vector2D(self.0 / rhs, self.1 / rhs)
    }
}

impl std::cmp::PartialEq for Vector2D {
    fn eq(&self, other: &Self) -> bool {
        let x = (self.0 - other.0).abs();
        let y = (self.1 - other.1).abs();
        x < EPS && y < EPS
    }
}

#[derive(Clone, Copy)]
struct Triangle {
    x: Vector2D,
    y: Vector2D,
    z: Vector2D,
}

impl Triangle {
    pub fn exists(&self) -> bool {
        let a = (self.y - self.z).len();
        let b = (self.x - self.z).len();
        let c = (self.x - self.y).len();
        if a + b - c < EPS {
            return false;
        }
        if b + c - a < EPS {
            return false;
        }
        if c + a - b < EPS {
            return false;
        }
        true
    }
}

#[derive(Debug, Clone, Copy)]
pub struct Circle {
    center: Vector2D,
    radius: f64,
}

impl Circle {
    pub fn inner_circle(a: Vector2D, b: Vector2D, c: Vector2D) -> Option<Circle> {
        let tri = Triangle { x: a, y: b, z: c };
        if !tri.exists() {
            return None;
        }

        let a_bisect = Line2D::pd(a, Vector2D::bisect(a - b, a - c));
        let b_bisect = Line2D::pd(b, Vector2D::bisect(b - a, b - c));

        let center = Line2D::intersection(a_bisect, b_bisect);
        let ab = Line2D::pd(a, b - a);
        let radius = ab.distance(center);
        Some(Circle {
            center: center,
            radius: radius,
        })
    }
    pub fn outer_circle(x: Vector2D, y: Vector2D, z: Vector2D) -> Option<Circle> {
        let a = (y - z).len();
        let a2 = a * a;
        let b = (x - z).len();
        let b2 = b * b;
        let c = (x - y).len();
        let c2 = c * c;

        if a + b - c < EPS {
            return None;
        }
        if b + c - a < EPS {
            return None;
        }
        if c + a - b < EPS {
            return None;
        }

        let X = x * (a2 * (b2 + c2 - a2)) + y * (b2 * (c2 + a2 - b2)) + z * (c2 * (a2 + b2 - c2));
        let Y = a2 * (b2 + c2 - a2) + b2 * (c2 + a2 - b2) + c2 * (a2 + b2 - c2);
        let center = X / Y;
        let radius = (x - center).len();
        Some(Circle {
            center: center,
            radius: radius,
        })
    }
    pub fn intersection(c1: &Self, c2: &Self) -> Vec<Vector2D> {
        let d = c1.center.dist(c2.center);
        if d > c1.radius + c2.radius + EPS {
            return vec![];
        }
        if c1.center == c2.center {
            return vec![];
        }
        let rc: f64 = (d * d + c1.radius * c1.radius - c2.radius * c2.radius) / (2. * d);
        let rs: f64 = f64::sqrt(c1.radius * c1.radius - rc * rc);
        let diff: Vector2D = (c2.center - c1.center) / d;
        let p1 = c1.center + diff.complex_mul(Vector2D(rc, rs));
        let p2 = c1.center + diff.complex_mul(Vector2D(rc, -rs));
        if p1 == p2 {
            vec![p1]
        } else {
            vec![p1, p2]
        }
    }
}
#[test]
fn test_inner_circle() {
    let p1 = Vector2D(0., 0.);
    let p2 = Vector2D(0., 1.);
    let p3 = Vector2D(1., 0.);
    let ic = Circle::inner_circle(p1, p2, p1);
    dbg!(&ic);
    let ic = Circle::inner_circle(p1, p2, p3);
    dbg!(&ic);
}
#[test]
fn test_outer_circle() {
    let p1 = Vector2D(0., 0.);
    let p2 = Vector2D(0., 1.);
    let p3 = Vector2D(1., 0.);
    let ic = Circle::outer_circle(p1, p2, p1);
    dbg!(&ic);
    let ic = Circle::outer_circle(p1, p2, p3);
    dbg!(&ic);
}
#[test]
fn test_circle_intersection() {
    let c1 = Circle {
        center: Vector2D(1., 0.),
        radius: 2.,
    };
    let c2 = Circle {
        center: Vector2D(-1., 0.),
        radius: 2.,
    };
    dbg!(Circle::intersection(&c1, &c1));
    dbg!(Circle::intersection(&c1, &c2));
    let c1 = Circle {
        center: Vector2D(1., 0.),
        radius: 1.,
    };
    let c2 = Circle {
        center: Vector2D(-1., 0.),
        radius: 1.,
    };
    dbg!(Circle::intersection(&c1, &c2));
    let c1 = Circle {
        center: Vector2D(1., 0.),
        radius: 0.8,
    };
    let c2 = Circle {
        center: Vector2D(-1., 0.),
        radius: 0.8,
    };
    dbg!(Circle::intersection(&c1, &c2));
}

/// Is line a-b and line c-d intersected ?

pub fn is_intersected(a: Vector2D, b: Vector2D, c: Vector2D, d: Vector2D) -> bool {
    let ta = (c.0 - d.0) * (a.1 - c.1) + (c.1 - d.1) * (c.0 - a.0);
    let tb = (c.0 - d.0) * (b.1 - c.1) + (c.1 - d.1) * (c.0 - b.0);
    let tc = (a.0 - b.0) * (c.1 - a.1) + (a.1 - b.1) * (a.0 - c.0);
    let td = (a.0 - b.0) * (d.1 - a.1) + (a.1 - b.1) * (a.0 - d.0);

    tc * td <= 0.0 && ta * tb <= 0.0
    // Not intersects start or end point.
    // tc * td < 0.0 && ta * tb < 0.0
}

#[derive(Clone, Copy, Debug)]
pub struct Line2D {
    p: Vector2D,
    d: Vector2D,
}

impl Line2D {
    pub fn pd(p: Vector2D, d: Vector2D) -> Self {
        Line2D { p: p, d: d.unit() }
    }
    pub fn from_two_points(a: Vector2D, b: Vector2D) -> Self {
        Line2D { p: a, d: b - a }
    }
    pub fn intersection(a: Line2D, b: Line2D) -> Vector2D {
        let n = b.d.normal();
        let x = n.dot(b.p - a.p) / n.dot(a.d);
        a.p + a.d * x
    }
    pub fn distance(self, a: Vector2D) -> f64 {
        let perpendicular = Self::pd(a, self.d.normal());
        let q = Self::intersection(self, perpendicular);
        (a - q).len()
    }
}
#[test]
fn test_line_intersection() {
    let m = Line2D::pd(Vector2D(0., 0.), Vector2D(1., 1.));
    let l1 = Line2D::pd(Vector2D(0., 2.), Vector2D(1., 0.));
    let l2 = Line2D::pd(Vector2D(0., 2.), Vector2D(1., -1.));
    let p1 = Line2D::intersection(m, l1);
    let p2 = Line2D::intersection(m, l2);
    assert_eq!(p1, Vector2D(2., 2.));
    assert_eq!(p2, Vector2D(1., 1.));
}
#[test]
fn test_line_distance() {
    let l = Line2D::from_two_points(Vector2D(-1., 1.), Vector2D(1., 1.));
    let p = Vector2D(0., 0.);
    assert_eq!(l.distance(p), 1.);
}

#[derive(PartialEq, PartialOrd)]
/// Implement Eq and Ord for a type which has only PartialEq and PartialOrd.
/// It is useful when sorting a Vec of f64
pub struct Total<T>(pub T);

impl<T: PartialEq> Eq for Total<T> {}

impl<T: PartialOrd> Ord for Total<T> {
    fn cmp(&self, other: &Total<T>) -> Ordering {
        self.0.partial_cmp(&other.0).unwrap()
    }
}
#[allow(dead_code)]
fn convex_hull(vs: &[Vector2D]) -> Vec<usize> {
    let mut idx: Vec<usize> = (0..vs.len()).collect();
    idx.sort_by_key(|&i| Total((vs[i].0, vs[i].1)));

    let mut res = Vec::new();

    for &i in &idx {
        while res.len() > 1
            && Vector2D::det(
                vs[res[res.len() - 1]] - vs[res[res.len() - 2]],
                vs[i] - vs[res[res.len() - 1]],
            ) <= 0.0
        {
            res.pop();
        }
        res.push(i);
    }
    let t = res.len();

    for &i in idx.iter().rev().skip(1) {
        while res.len() > t
            && (vs[res[res.len() - 1]] - vs[res[res.len() - 2]]).det(vs[i] - vs[res[res.len() - 1]])
                <= 0.0
        {
            res.pop();
        }
        res.push(i);
    }

    res.pop();
    res
}
#[test]
fn test_convex_hull() {
    let vs = vec![
        Vector2D(-1.0, -1.0),
        Vector2D(-1.0, 1.0),
        Vector2D(1.0, 1.0),
        Vector2D(1.0, -1.0),
        Vector2D(0.0, 0.0),
        Vector2D(0.1, 0.1),
    ];

    let mut idx = convex_hull(&vs);
    idx.sort();

    assert_eq!(&idx, &[0, 1, 2, 3]);
}

pub fn closest_pair(ps: &[(f64, f64)]) -> ((f64, f64), (f64, f64)) {
    fn d(p1: (f64, f64), p2: (f64, f64)) -> f64 {
        ((p1.0 - p2.0).powi(2) + (p1.1 - p2.1).powi(2)).sqrt()
    }

    fn rec(x_sort: &[(f64, f64)], y_sort: &[(f64, f64)]) -> ((f64, f64), (f64, f64)) {
        if x_sort.len() <= 3 {
            let mut min_d = std::f64::MAX;
            let mut pair = ((0.0, 0.0), (0.0, 0.0));
            for (i, &p1) in x_sort.iter().enumerate() {
                for (j, &p2) in x_sort.iter().enumerate() {
                    if i != j {
                        let dist = d(p1, p2);
                        if dist < min_d {
                            min_d = dist;
                            pair = (p1, p2);
                        }
                    }
                }
            }

            return pair;
        }

        let mid = x_sort.len() / 2;
        let pivot = x_sort[mid].0;

        let q_x = &x_sort[..mid];
        let r_x = &x_sort[mid..];

        let mut q_y = Vec::with_capacity(mid);
        let mut r_y = Vec::with_capacity(x_sort.len() - mid);

        for &(x, y) in y_sort {
            if x < pivot {
                q_y.push((x, y));
            } else {
                r_y.push((x, y));
            }
        }

        let pair1 = rec(q_x, &q_y);
        let pair2 = rec(r_x, &r_y);

        let w = d(pair1.0, pair1.1).min(d(pair2.0, pair2.1));
        let s: Vec<(f64, f64)> = y_sort
            .iter()
            .filter(|&&(x, _)| (pivot - x).abs() <= w)
            .cloned()
            .collect();

        let mut min_d = w;
        let mut pair = if d(pair1.0, pair1.1) < d(pair2.0, pair2.1) {
            pair1
        } else {
            pair2
        };

        for (i, &p1) in s.iter().enumerate() {
            for &p2 in s[i + 1..].iter().take(15) {
                let dist = d(p1, p2);
                if dist < min_d {
                    min_d = dist;
                    pair = (p1, p2);
                }
            }
        }
        pair
    }

    let mut x_sort = ps.to_vec();
    let mut y_sort = ps.to_vec();

    x_sort.sort_by_key(|p| Total(p.0));
    y_sort.sort_by_key(|p| Total(p.1));
    rec(&x_sort, &y_sort)
}

fn solve() {
    let (n, ii) = readuu();
    let mut vp = vec![];
    for i in 0..n {
        let p = readuu();
        vp.push(p);
    }
    let mut dp = vec![vec![0 as usize; (ii + 1) as usize]; (n + 1) as usize];
    for i in 0..n {
        for j in 0..ii + 1 {
            if j < vp[i].0 {
                dp[i + 1][j as usize] = dp[i][j as usize];
            } else {
                dp[i + 1][j as usize] =
                    std::cmp::max(dp[i][j as usize], dp[i][j as usize - vp[i].0] + vp[i].1);
            }
        }
    }
    let mut res = 0;
    for i in 0..=ii {
        res = std::cmp::max(res, dp[n][i as usize]);
    }
    println!("{}", res);
    return;
}