結果
問題 | No.798 コレクション |
ユーザー |
![]() |
提出日時 | 2022-06-10 12:19:29 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 7,474 bytes |
コンパイル時間 | 11,744 ms |
コンパイル使用メモリ | 379,200 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-21 05:43:50 |
合計ジャッジ時間 | 12,989 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
コンパイルメッセージ
warning: unused macro definition: `input_inner` --> src/main.rs:89:14 | 89 | macro_rules! input_inner { | ^^^^^^^^^^^ | = note: `#[warn(unused_macros)]` on by default warning: unused macro definition: `mydbg` --> src/main.rs:142:14 | 142 | macro_rules! mydbg { | ^^^^^ warning: unused macro definition: `max` --> src/main.rs:237:15 | 237 | macro_rules ! max { ( x ) ; ( ( $xs : expr ) ,+ ) => { { std :: cmp :: max ( $x , max! ( $ ( $xs ) ,+ ) ... | ^^^ warning: unused macro definition: `chmax` --> src/main.rs:252:14 | 252 | macro_rules! chmax { | ^^^^^ warning: unused macro definition: `chadd` --> src/main.rs:264:14 | 264 | macro_rules! chadd { | ^^^^^ warning: unused macro definition: `chsub` --> src/main.rs:270:14 | 270 | macro_rules! chsub { | ^^^^^ warning: unused macro definition: `chmul` --> src/main.rs:275:14 | 275 | macro_rules! chmul { | ^^^^^
ソースコード
#![allow(unused_parens)]#![allow(unused_imports)]#![allow(non_upper_case_globals)]#![allow(non_snake_case)]#![allow(unused_mut)]#![allow(unused_variables)]#![allow(dead_code)]type Vec2<T> = Vec<Vec<T>>;type Vec3<T> = Vec<Vec<Vec<T>>>;#[allow(unused_macros)]macro_rules! invec {( $ t : ty ) => {{let mut s = String::new();match std::io::stdin().read_line(&mut s) {Ok(0) => Vec::<$t>::new(),Ok(n) => s.trim().split_whitespace().map(|s| s.parse::<$t>().unwrap()).collect::<Vec<$t>>(),Err(_) => Vec::<$t>::new(),}}};}#[allow(unused_macros)]macro_rules! get {($t:ty) => {{let mut line: String = String::new();std::io::stdin().read_line(&mut line).unwrap();line.trim().parse::<$t>().unwrap()}};($($t:ty),*) => {{let mut line: String = String::new();std::io::stdin().read_line(&mut line).unwrap();let mut iter = line.split_whitespace();($(iter.next().unwrap().parse::<$t>().unwrap(),)*)}};($t:ty; $n:expr) => {(0..$n).map(|_|get!($t)).collect::<Vec<_>>()};($($t:ty),*; $n:expr) => {(0..$n).map(|_|get!($($t),*)).collect::<Vec<_>>()};($t:ty ;;) => {{let mut line: String = String::new();std::io::stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t| t.parse::<$t>().unwrap()).collect::<Vec<_>>()}};($t:ty ;; $n:expr) => {(0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()};}#[allow(unused_macros)]macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let mut s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {let mut $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}#[allow(unused_macros)]macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($next:expr, [$t:tt]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}#[allow(unused_macros)]#[cfg(debug_assertions)]macro_rules! mydbg {//($arg:expr) => (dbg!($arg))//($arg:expr) => (println!("{:?}",$arg));($($a:expr),*) => {eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);}}#[cfg(not(debug_assertions))]macro_rules! mydbg {($($arg:expr),*) => {};}macro_rules! echo {($($a:expr),*) => {$(println!("{}",$a))*}}use std::cmp::*;use std::collections::*;use std::ops::{Add, Div, Mul, Rem, Sub};trait SafeRangeContain {fn safe_contains(&self, x: i64) -> bool;}impl SafeRangeContain for std::ops::Range<usize> {fn safe_contains(&self, x: i64) -> bool {if x < 0 {return false;}return self.contains(&(x as usize));}}#[allow(dead_code)]static INF_I64: i64 = i64::max_value() / 2;#[allow(dead_code)]static INF_I32: i32 = i32::max_value() / 2;#[allow(dead_code)]static INF_USIZE: usize = usize::max_value() / 2;#[allow(dead_code)]static M_O_D: usize = 1000000007;#[allow(dead_code)]static PAI: f64 = 3.1415926535897932;trait IteratorExt: Iterator {fn toVec(self) -> Vec<Self::Item>;}impl<T: Iterator> IteratorExt for T {fn toVec(self) -> Vec<Self::Item> {self.collect()}}trait CharExt {fn toNum(&self) -> usize;fn toAlphabetIndex(&self) -> usize;fn toNumIndex(&self) -> usize;}impl CharExt for char {fn toNum(&self) -> usize {return *self as usize;}fn toAlphabetIndex(&self) -> usize {return self.toNum() - 'a' as usize;}fn toNumIndex(&self) -> usize {return self.toNum() - '0' as usize;}}trait VectorExt {fn joinToString(&self, s: &str) -> String;}impl<T: ToString> VectorExt for Vec<T> {fn joinToString(&self, s: &str) -> String {return self.iter().map(|x| x.to_string()).collect::<Vec<_>>().join(s);}}trait StringExt {fn get_reverse(&self) -> String;}impl StringExt for String {fn get_reverse(&self) -> String {self.chars().rev().collect::<String>()}}trait UsizeExt {fn pow(&self, n: usize) -> usize;}impl UsizeExt for usize {fn pow(&self, n: usize) -> usize {return ((*self as u64).pow(n as u32)) as usize;}}macro_rules ! max { ( $x : expr ) => ( $x ) ; ( $x : expr , $ ( $xs : expr ) ,+ ) => { { std :: cmp :: max ( $x , max! ( $ ( $xs ) ,+ ) ) } } ; }macro_rules ! min { ( $x : expr ) => ( $x ) ; ( $x : expr , $ ( $xs : expr ) ,+ ) => { { std :: cmp :: min ( $x , min! ( $ ( $xs ) ,+ ) ) } } ; }macro_rules! chmin {($a:expr, $($b:expr),+) => {{let d = min!($($b),+);if $a > d {$a = d;true} else {false}}};}macro_rules! chmax {($a:expr, $($b:expr),+) => {{let d = max!($($b),+);if $a < d {$a = d;true} else {false}}};}macro_rules! chadd {($a:expr, $b:expr) => {{$a = $a + $b;}};}macro_rules! chsub {($a:expr, $b:expr) => {{$a = $a - $b;}};}macro_rules! chmul {($a:expr, $b:expr) => {{$a = $a * $b;}};}fn main() {solve();}fn solve() {let mut ans: u64 = 0;let N = get!(usize);let mut P = vec![];for _ in 0..N {P.push(get!(usize, usize));}P.sort_by_key(|x| Reverse(x.1));let mut dp = vec![usize::max_value() / 2; N + 1];dp[0] = 0;let mut count = 0;let mut sum = 0;for i in 0..N {sum += 1;if sum < N && i % 2 == 1 {sum += 1;count += 1;}let mut pre = vec![usize::max_value() / 2; N + 1];std::mem::swap(&mut dp, &mut pre);for j in 0..N {chmin!(dp[j], pre[j]);let (a, b) = P[i];chmin!(dp[j + 1], pre[j] + a + b * j);}}echo!(dp[N - count]);}