結果

問題 No.409 ダイエット
ユーザー koba-e964koba-e964
提出日時 2017-01-10 15:51:56
言語 Rust
(1.77.0)
結果
AC  
実行時間 75 ms / 2,000 ms
コード長 3,629 bytes
コンパイル時間 4,759 ms
コンパイル使用メモリ 137,488 KB
実行使用メモリ 10,524 KB
最終ジャッジ日時 2023-09-08 17:17:11
合計ジャッジ時間 6,731 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 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,384 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 0 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 0 ms
4,380 KB
testcase_12 AC 1 ms
4,376 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,380 KB
testcase_17 AC 1 ms
4,380 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 0 ms
4,376 KB
testcase_24 AC 0 ms
4,376 KB
testcase_25 AC 1 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,380 KB
testcase_29 AC 0 ms
4,376 KB
testcase_30 AC 1 ms
4,384 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 1 ms
4,380 KB
testcase_34 AC 1 ms
4,376 KB
testcase_35 AC 1 ms
4,376 KB
testcase_36 AC 1 ms
4,380 KB
testcase_37 AC 1 ms
4,376 KB
testcase_38 AC 2 ms
4,376 KB
testcase_39 AC 1 ms
4,376 KB
testcase_40 AC 2 ms
4,380 KB
testcase_41 AC 2 ms
4,376 KB
testcase_42 AC 1 ms
4,380 KB
testcase_43 AC 2 ms
4,376 KB
testcase_44 AC 2 ms
4,380 KB
testcase_45 AC 1 ms
4,380 KB
testcase_46 AC 1 ms
4,380 KB
testcase_47 AC 1 ms
4,380 KB
testcase_48 AC 1 ms
4,376 KB
testcase_49 AC 2 ms
4,376 KB
testcase_50 AC 2 ms
4,376 KB
testcase_51 AC 2 ms
4,376 KB
testcase_52 AC 2 ms
4,380 KB
testcase_53 AC 2 ms
4,376 KB
testcase_54 AC 1 ms
4,380 KB
testcase_55 AC 22 ms
5,792 KB
testcase_56 AC 38 ms
6,072 KB
testcase_57 AC 44 ms
10,524 KB
testcase_58 AC 19 ms
5,468 KB
testcase_59 AC 27 ms
6,124 KB
testcase_60 AC 17 ms
5,104 KB
testcase_61 AC 38 ms
9,080 KB
testcase_62 AC 41 ms
10,248 KB
testcase_63 AC 38 ms
8,860 KB
testcase_64 AC 21 ms
5,464 KB
testcase_65 AC 40 ms
7,740 KB
testcase_66 AC 43 ms
9,584 KB
testcase_67 AC 32 ms
8,196 KB
testcase_68 AC 27 ms
6,080 KB
testcase_69 AC 38 ms
8,492 KB
testcase_70 AC 61 ms
8,576 KB
testcase_71 AC 34 ms
5,664 KB
testcase_72 AC 75 ms
10,432 KB
testcase_73 AC 68 ms
8,192 KB
testcase_74 AC 44 ms
6,952 KB
testcase_75 AC 69 ms
8,772 KB
testcase_76 AC 50 ms
7,612 KB
testcase_77 AC 33 ms
4,820 KB
testcase_78 AC 38 ms
6,404 KB
testcase_79 AC 31 ms
5,116 KB
testcase_80 AC 71 ms
9,876 KB
testcase_81 AC 69 ms
8,416 KB
testcase_82 AC 50 ms
7,424 KB
testcase_83 AC 55 ms
7,664 KB
testcase_84 AC 45 ms
5,704 KB
testcase_85 AC 6 ms
4,376 KB
testcase_86 AC 44 ms
5,956 KB
testcase_87 AC 61 ms
8,832 KB
testcase_88 AC 25 ms
4,380 KB
testcase_89 AC 51 ms
5,396 KB
testcase_90 AC 23 ms
4,376 KB
testcase_91 AC 55 ms
5,604 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[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: i64, // current position (x)
    cur_idx: usize, // current index (in 0 .. dat.len())
}

impl ConvexHullTrick {
    fn new(minimum: i64) -> Self {
        ConvexHullTrick { dat: Vec::new(), cur: minimum, 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()
    }
    fn query(&mut self, x: i64) -> i64 {
        assert!(x >= self.cur);
        self.cur = x;
        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];
        return 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 + 1];
    // 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(MINF);
    dp[0] = 0;
    for i in 1 .. (n + 2) {
        let t = i as i64 - 1;
        cht.add((b * (2 * t + 1), -2 * dp[i - 1] - b * t * (t + 1) - 2 * a * t));
        if i == n + 1 {
            break;
        }
        let ii = i as i64;
        let tmp =
            -cht.query(ii) + 2 * d[i - 1] - 2 * a * (ii - 1) + b * ii * ii;
        assert!(tmp % 2 == 0);
        dp[i] = tmp / 2;
    }
    let ni = n as i64 + 1;
    let tmp = -cht.query(ni) - 2 * a * (ni - 1) + b * ni * ni;
    assert!(tmp % 2 == 0);
    println!("{}", w + tmp / 2);
}
0