結果

問題 No.1541 ゅゅさんのテスト勉強
ユーザー 57tggx
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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)
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0