結果

問題 No.703 ゴミ拾い Easy
ユーザー snteasntea
提出日時 2018-08-18 00:06:29
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 57 ms / 1,500 ms
コード長 3,727 bytes
コンパイル時間 15,464 ms
コンパイル使用メモリ 378,068 KB
実行使用メモリ 16,472 KB
最終ジャッジ日時 2024-12-14 05:22:36
合計ジャッジ時間 19,332 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,816 KB
testcase_02 AC 1 ms
6,820 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,820 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 1 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,820 KB
testcase_12 AC 1 ms
6,820 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 1 ms
6,820 KB
testcase_15 AC 1 ms
6,816 KB
testcase_16 AC 1 ms
6,816 KB
testcase_17 AC 1 ms
6,820 KB
testcase_18 AC 1 ms
6,816 KB
testcase_19 AC 1 ms
6,820 KB
testcase_20 AC 1 ms
6,820 KB
testcase_21 AC 2 ms
6,816 KB
testcase_22 AC 2 ms
6,816 KB
testcase_23 AC 1 ms
6,816 KB
testcase_24 AC 56 ms
13,920 KB
testcase_25 AC 57 ms
13,680 KB
testcase_26 AC 55 ms
14,008 KB
testcase_27 AC 55 ms
13,944 KB
testcase_28 AC 55 ms
12,996 KB
testcase_29 AC 54 ms
14,256 KB
testcase_30 AC 54 ms
14,072 KB
testcase_31 AC 57 ms
14,880 KB
testcase_32 AC 54 ms
14,192 KB
testcase_33 AC 55 ms
13,996 KB
testcase_34 AC 44 ms
11,560 KB
testcase_35 AC 44 ms
12,716 KB
testcase_36 AC 44 ms
11,820 KB
testcase_37 AC 44 ms
11,820 KB
testcase_38 AC 46 ms
11,692 KB
testcase_39 AC 45 ms
13,428 KB
testcase_40 AC 44 ms
11,308 KB
testcase_41 AC 44 ms
11,816 KB
testcase_42 AC 47 ms
13,240 KB
testcase_43 AC 44 ms
11,432 KB
testcase_44 AC 1 ms
6,820 KB
testcase_45 AC 1 ms
6,820 KB
testcase_46 AC 48 ms
16,472 KB
testcase_47 AC 46 ms
11,864 KB
testcase_48 AC 1 ms
6,820 KB
testcase_49 AC 2 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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()-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