結果
問題 | 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)}