結果

問題 No.703 ゴミ拾い Easy
コンテスト
ユーザー sntea
提出日時 2018-08-18 00:02:38
言語 Rust
(1.83.0 + proconio)
結果
RE  
実行時間 -
コード長 3,725 bytes
コンパイル時間 15,890 ms
コンパイル使用メモリ 392,232 KB
実行使用メモリ 16,364 KB
最終ジャッジ日時 2024-10-11 06:08:47
合計ジャッジ時間 19,694 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused macro definition: `printf`
   --> src/main.rs:133:18
    |
133 |     macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    |                  ^^^^^^
    |
    = note: `#[warn(unused_macros)]` on by default

ソースコード

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