結果
問題 | No.1541 ゅゅさんのテスト勉強 |
ユーザー |
![]() |
提出日時 | 2021-06-06 17:39:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,562 bytes |
コンパイル時間 | 15,681 ms |
コンパイル使用メモリ | 378,268 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-11-23 01:14:30 |
合計ジャッジ時間 | 56,797 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 14 WA * 3 TLE * 14 |
ソースコード
struct Info { k: usize, c: i64, v: Vec<(usize, i64)>, } struct Input { n: usize, m: i64, info: Vec<Info>, } fn main() { let Input { n, m, info } = Input::read(std::io::stdin().lock()); assert!(matches!(n, 1..=100)); assert!(matches!(m, 0..=1_000_000_000)); assert_eq!(n, info.len()); for (i, Info { k, c, v }) in info.iter().enumerate() { assert!(*k < n); assert!(matches!(c, 0..=1_000_000_000)); assert_eq!(*k, v.len()); for (a, b) in v { assert!(*a < n); assert!(*a != i); assert!(matches!(b, 0..=1_000_000_000)); } assert!(v.windows(2).all(|x| x[0].0 < x[1].0)); } let mut ans = 0; for i in 0i64..1 << n { let mut tmp = m * i.count_ones() as i64; for (j, Info { c, .. }) in info.iter().enumerate() { if i >> j & 1 == 1 { tmp -= c; } } for (j, Info { v, .. }) in info.iter().enumerate() { if i >> j & 1 == 1 { for (a, b) in v { if i >> a & 1 == 1 { tmp += b; } } } } ans = ans.max(tmp); } println!("{}", ans); } impl Input { fn read<T: std::io::BufRead>(mut input: T) -> Input { let (n, m) = { let mut buffer = String::new(); input.read_line(&mut buffer).unwrap(); match &split(&buffer).unwrap()[..] { [n, m] => (n.parse().unwrap(), m.parse().unwrap()), _ => panic!("input format error: N M"), } }; let info = { let mut info = Vec::with_capacity(n); for _ in 0..n { let mut buffer = String::new(); input.read_line(&mut buffer).unwrap(); let (k, c) = match &split(&buffer).unwrap()[..] { [k, c] => (k.parse().unwrap(), c.parse().unwrap()), _ => panic!("input format error: k C"), }; let v = if k == 0 { Vec::new() } else { let mut a = String::new(); input.read_line(&mut a).unwrap(); let a = split(&a).unwrap(); let mut b = String::new(); input.read_line(&mut b).unwrap(); let b = split(&b).unwrap(); let v = a .iter() .zip(&b) .map(|(x, y)| (x.parse::<usize>().unwrap() - 1, y.parse().unwrap())) .collect(); v }; info.push(Info { k: k, c: c, v: v }); } info }; Input { n: n, m: m, info: info, } } } fn split(s: &str) -> Option<Vec<&str>> { enum State { Word(usize), Space, End, } let mut state = State::Word(0); let mut ret = Vec::new(); for (i, c) in s.char_indices() { let prev = match state { State::End => return None, State::Word(i) => i, State::Space => { state = State::Word(i); i } }; if c == ' ' || c == '\n' { ret.push(&s[prev..i]); state = if c == ' ' { State::Space } else { State::End }; } } matches!(state, State::End).then(|| ret) }