結果

問題 No.703 ゴミ拾い Easy
ユーザー snteasntea
提出日時 2018-08-18 00:06:29
言語 Rust
(1.77.0)
結果
AC  
実行時間 55 ms / 1,500 ms
コード長 3,727 bytes
コンパイル時間 2,023 ms
コンパイル使用メモリ 152,752 KB
実行使用メモリ 15,196 KB
最終ジャッジ日時 2023-08-30 18:59:48
合計ジャッジ時間 5,324 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,376 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 1 ms
4,384 KB
testcase_24 AC 54 ms
13,028 KB
testcase_25 AC 54 ms
14,984 KB
testcase_26 AC 54 ms
12,580 KB
testcase_27 AC 53 ms
12,684 KB
testcase_28 AC 54 ms
13,676 KB
testcase_29 AC 54 ms
12,692 KB
testcase_30 AC 54 ms
14,928 KB
testcase_31 AC 55 ms
15,196 KB
testcase_32 AC 54 ms
13,732 KB
testcase_33 AC 53 ms
12,652 KB
testcase_34 AC 43 ms
11,632 KB
testcase_35 AC 44 ms
12,600 KB
testcase_36 AC 43 ms
11,852 KB
testcase_37 AC 44 ms
11,792 KB
testcase_38 AC 44 ms
11,824 KB
testcase_39 AC 44 ms
13,068 KB
testcase_40 AC 43 ms
11,400 KB
testcase_41 AC 44 ms
11,916 KB
testcase_42 AC 45 ms
12,552 KB
testcase_43 AC 43 ms
11,564 KB
testcase_44 AC 1 ms
4,380 KB
testcase_45 AC 1 ms
4,380 KB
testcase_46 AC 43 ms
14,132 KB
testcase_47 AC 45 ms
11,964 KB
testcase_48 AC 1 ms
4,376 KB
testcase_49 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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()-1 {
        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