結果

問題 No.703 ゴミ拾い Easy
ユーザー snteasntea
提出日時 2018-08-18 00:02:38
言語 Rust
(1.77.0)
結果
RE  
実行時間 -
コード長 3,725 bytes
コンパイル時間 4,154 ms
コンパイル使用メモリ 174,756 KB
実行使用メモリ 16,228 KB
最終ジャッジ日時 2024-04-19 13:42:54
合計ジャッジ時間 8,402 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused macro definition: `printf`
   --> main.rs:133:18
    |
133 |     macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    |                  ^^^^^^
    |
    = note: `#[warn(unused_macros)]` on by default

warning: 1 warning emitted

ソースコード

diff # 

#[allow(dead_code)]
fn getline() -> String {
    let mut res = String::new();
    std::io::stdin().read_line(&mut res).ok();
    res
}

#[allow(unused_macros)]
macro_rules! readl {
    ($t: ty) => {
        {
            let s = getline();
            s.trim().parse::<$t>().unwrap()
        }
    };
    ($( $t: ty),+ ) => {
        {
            let s = getline();
            let mut iter = s.trim().split(' ');
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*)
        }
    };
}

#[allow(unused_macros)]
macro_rules! readlvec {
    ($t:ty) => {{
        let s = getline();
        let iter = s.trim().split(' ');
        iter.map(|x| x.parse().unwrap()).collect::<Vec<$t>>()
    }};
}

#[allow(unused_macros)]
macro_rules! debug {
    ($x:expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    };
}
// macro_rules! debug { ($x: expr) => () }

#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
    T: Iterator,
    T::Item: std::fmt::Display,
{
    let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
    res.pop();
    res
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};

#[derive(Clone)]
struct ConvexHullTrick<T> {
    lines: Vec<(T, T)>,
}

impl<T> ConvexHullTrick<T>
where
    T: std::ops::Add<Output = T>
        + std::ops::Mul<Output = T>
        + std::ops::Sub<Output = T>
        + Copy
        + PartialOrd,
{
    fn new() -> Self {
        ConvexHullTrick { lines: Vec::new() }
    }

    fn check<'a>(mut l1: &'a (T, T), l2: &(T, T), mut l3: &'a (T, T)) -> bool {
        if l1 < l3 {
            std::mem::swap(&mut l1, &mut l3);
        }
        (l3.1 - l2.1) * (l2.0 - l1.0) >= (l2.1 - l1.1) * (l3.0 - l2.0)
    }

    fn add(&mut self, a: T, b: T) {
        while self.lines.len() >= 2
            && Self::check(
                &self.lines[self.lines.len() - 2],
                self.lines.last().expect("cht Error!!"),
                &(a, b),
            ) {
            self.lines.pop();
        }
        self.lines.push((a, b));
    }

    fn calc(&self, i: usize, x: T) -> T {
        self.lines[i].0 * x + self.lines[i].1
    }

    fn query(&self, x: T) -> T {
        if self.lines.len() == 1 {
            return self.calc(0, x);
        }

        let mut ng = 0;
        let mut ok = self.lines.len();
        let check = |i| {
            if i + 1 == self.lines.len() {
                true
            } else {
                self.calc(i, x) < self.calc(i + 1, x)
            }
        };
        if check(ng) {
            return self.calc(ng, x);
        }
        while ok-ng > 1 {
            let m = (ok + ng) / 2;
            if check(m) {
                ok = m;
            } else {
                ng = m;
            }
        }
        self.calc(ok, x)
    }
}

fn main() {
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }


    let n = readl!(usize);
    let a = readlvec!(i64);
    let x = readlvec!(i64);
    let y = readlvec!(i64);

    let inf = 1_000_000_000_000_000;
    let mut dp = vec![inf; n+1];
    dp[0] = 0;
    let mut cht = ConvexHullTrick::new();
    for i in 0..dp.len() {
        cht.add(x[i], dp[i] + x[i] * x[i] + y[i] * y[i]);
        dp[i+1] = min(dp[i+1], cht.query(-2 * a[i]) + a[i] * a[i]);
    }
    printfln!("{}", dp.last().unwrap());
}
0