#143866 (Rust) No.409 ダイエット

提出ソース

結果

問題	No.409 ダイエット
ユーザー	koba-e964
提出日時	2017-01-10 15:58:03
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	76 ms / 2,000 ms
コード長	3,567 bytes
コンパイル時間	22,693 ms
コンパイル使用メモリ	400,416 KB
実行使用メモリ	10,496 KB
最終ジャッジ日時	2024-06-26 10:08:09
合計ジャッジ時間	19,218 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	1 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	1 ms 5,376 KB
testcase_13	AC	1 ms 5,376 KB
testcase_14	AC	1 ms 5,376 KB
testcase_15	AC	1 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	1 ms 5,376 KB
testcase_19	AC	1 ms 5,376 KB
testcase_20	AC	1 ms 5,376 KB
testcase_21	AC	1 ms 5,376 KB
testcase_22	AC	1 ms 5,376 KB
testcase_23	AC	1 ms 5,376 KB
testcase_24	AC	1 ms 5,376 KB
testcase_25	AC	1 ms 5,376 KB
testcase_26	AC	1 ms 5,376 KB
testcase_27	AC	1 ms 5,376 KB
testcase_28	AC	1 ms 5,376 KB
testcase_29	AC	1 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	1 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
testcase_33	AC	1 ms 5,376 KB
testcase_34	AC	1 ms 5,376 KB
testcase_35	AC	1 ms 5,376 KB
testcase_36	AC	1 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	1 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	2 ms 5,376 KB
testcase_47	AC	1 ms 5,376 KB
testcase_48	AC	1 ms 5,376 KB
testcase_49	AC	2 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	1 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB
testcase_54	AC	1 ms 5,376 KB
testcase_55	AC	22 ms 5,888 KB
testcase_56	AC	38 ms 6,144 KB
testcase_57	AC	44 ms 10,496 KB
testcase_58	AC	19 ms 5,504 KB
testcase_59	AC	28 ms 6,144 KB
testcase_60	AC	17 ms 5,376 KB
testcase_61	AC	39 ms 9,088 KB
testcase_62	AC	41 ms 10,112 KB
testcase_63	AC	38 ms 8,832 KB
testcase_64	AC	21 ms 5,504 KB
testcase_65	AC	40 ms 7,680 KB
testcase_66	AC	43 ms 9,600 KB
testcase_67	AC	33 ms 8,192 KB
testcase_68	AC	27 ms 6,272 KB
testcase_69	AC	38 ms 8,448 KB
testcase_70	AC	62 ms 8,576 KB
testcase_71	AC	39 ms 5,760 KB
testcase_72	AC	76 ms 10,240 KB
testcase_73	AC	69 ms 8,064 KB
testcase_74	AC	44 ms 6,912 KB
testcase_75	AC	70 ms 8,576 KB
testcase_76	AC	51 ms 7,552 KB
testcase_77	AC	34 ms 5,376 KB
testcase_78	AC	39 ms 6,528 KB
testcase_79	AC	31 ms 5,376 KB
testcase_80	AC	73 ms 9,728 KB
testcase_81	AC	70 ms 8,320 KB
testcase_82	AC	52 ms 7,552 KB
testcase_83	AC	55 ms 7,552 KB
testcase_84	AC	45 ms 5,888 KB
testcase_85	AC	6 ms 5,376 KB
testcase_86	AC	44 ms 5,888 KB
testcase_87	AC	62 ms 8,704 KB
testcase_88	AC	26 ms 5,376 KB
testcase_89	AC	52 ms 5,376 KB
testcase_90	AC	25 ms 5,376 KB
testcase_91	AC	55 ms 5,760 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    return ret;
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.is_err() || res.ok().unwrap() == 0 || u8b[0] <= ' ' as u8 {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = std::string::String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}
fn parse<T: std::str::FromStr>(s: &str) -> T { s.parse::<T>().ok().unwrap() }

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { parse(&get_word()) }

/*
 * Manages multiple linear graphs.
 * Lines that are not necessary to calculate maximum values are deleted.
 */
struct ConvexHullTrick {
    dat: Vec<(i64, i64)>, // (a,b) -> y = a * x + b
    cur_idx: usize, // current index (in 0 .. dat.len())
}

impl ConvexHullTrick {
    fn new() -> Self {
        ConvexHullTrick { dat: Vec::new(), cur_idx: 0, }
    }
    fn check(a: (i64, i64), b: (i64, i64), c: (i64, i64)) -> bool {
        (b.0 - a.0) * (c.1 - b.1) >= (b.1 - a.1) * (c.0 - b.0)
    }
    /*
     * added.0 must be the largest.
     */
    fn add(&mut self, added: (i64, i64)) {
        while self.dat.len() >= 2 {
            let l = self.dat.len();
            if Self::check(self.dat[l - 2], self.dat[l - 1], added) {
                if self.cur_idx == self.dat.len() - 1 {
                    self.cur_idx -= 1;
                }
                self.dat.pop().unwrap();
            } else {
                break;
            }
        }
        self.dat.push(added);
    }
    #[allow(dead_code)]
    fn get(&self) -> Vec<(i64, i64)> {
        self.dat.clone()
    }
    // The caller must ensure that x is increasing,
    // when calls are sorted in chronological order.
    fn query(&mut self, x: i64) -> i64 {
        let n = self.dat.len();
        while self.cur_idx < n - 1 {
            let line = self.dat[self.cur_idx];
            let line2 = self.dat[self.cur_idx + 1];
            if line.0 * x + line.1 < line2.0 * x + line2.1 {
                self.cur_idx += 1;
            } else {
                break;
            }
        }
        let line = self.dat[self.cur_idx];
        line.0 * x + line.1
    }
}

const MINF: i64 = -1_i64 << 60;

fn main() {
    let n: usize = get();
    let a: i64 = get();
    let b: i64 = get();
    let w: i64 = get();
    let d: Vec<i64> = (0 .. n).map(|_| get()).collect();
    let mut dp: Vec<i64> = vec![MINF; n + 2];
    // dp[0] = 0
    // dp[i] = d[i - 1] + min (dp[t] - a(i-t-1) + b * (i - t) * (i - t - 1) / 2)
    // 2dp[i] = d[i-1] - 2a(i-1) + bi^2 + min(2dp[t] + bt(t+1) + 2at - b(2t+1)i)
    let mut cht = ConvexHullTrick::new();
    dp[0] = 0;
    for i in 1 .. (n + 2) {
        let t = i as i64 - 1;
        // Signs are flipped because cht calculates the maximum value.
        cht.add((b * (2 * t + 1),
                 -2 * dp[i - 1] - b * t * (t + 1) - 2 * a * t));
        let ii = i as i64;
        let tmp =
            -cht.query(ii) + 2 * (if i == n + 1 { 0 } else { d[i - 1] })
            - 2 * a * (ii - 1) + b * ii * ii;
        assert!(tmp % 2 == 0);
        dp[i] = tmp / 2;
    }
    println!("{}", w + dp[n + 1]);
}

yukicoder

結果

テストケース

ソースコード