結果
問題 | No.1541 ゅゅさんのテスト勉強 |
ユーザー | 57tggx |
提出日時 | 2021-06-06 17:39:52 |
言語 | Rust (1.77.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,562 bytes |
コンパイル時間 | 5,019 ms |
コンパイル使用メモリ | 147,632 KB |
実行使用メモリ | 8,752 KB |
最終ジャッジ日時 | 2023-08-14 23:35:11 |
合計ジャッジ時間 | 5,046 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
8,752 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | TLE | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
ソースコード
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) }