結果
問題 | No.1703 Much Matching |
ユーザー |
|
提出日時 | 2022-10-02 02:18:47 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 1,158 bytes |
コンパイル時間 | 15,345 ms |
コンパイル使用メモリ | 377,996 KB |
実行使用メモリ | 33,152 KB |
最終ジャッジ日時 | 2024-12-24 09:38:53 |
合計ジャッジ時間 | 19,557 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
fn main() {let mut nmq = String::new();std::io::stdin().read_line(&mut nmq).ok();let nmq: Vec<usize> = nmq.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();let n = nmq[0];let m = nmq[1];let q = nmq[2];let queries = (0..q).map(|_| {let mut temp = String::new();std::io::stdin().read_line(&mut temp).ok();let temp: Vec<usize> = temp.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();(temp[0]-1, temp[1]-1)}).collect::<Vec<(usize, usize)>>();let mut checked = vec![vec![0usize; m]; n];let mut dp = vec![vec![0usize; m+1]; n+1];for &(a, b) in queries.iter() {checked[a][b] = 1;}for i in 0..=n {for j in 0..=m {if i + 1 <= n {dp[i+1][j] = dp[i+1][j].max(dp[i][j]);}if j + 1 <= m {dp[i][j+1] = dp[i][j+1].max(dp[i][j]);}if i + 1 <= n && j + 1 <= m {dp[i+1][j+1] = dp[i+1][j+1].max(dp[i][j] + checked[i][j]);}}}println!("{}", dp[n][m]);}