結果

問題 No.3257 +|+
ユーザー LyricalMaestro
提出日時 2025-09-07 10:26:13
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 2,281 ms / 3,000 ms
コード長 1,326 bytes
コンパイル時間 13,745 ms
コンパイル使用メモリ 395,184 KB
実行使用メモリ 190,904 KB
最終ジャッジ日時 2025-09-07 10:27:22
合計ジャッジ時間 62,363 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `n`
 --> src/main.rs:9:9
  |
9 |     let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
  |         ^ help: if this is intentional, prefix it with an underscore: `_n`
  |
  = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

use std::collections::HashMap;
use std::io::{self, BufRead};

fn main() {
    // 入力読み込み
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();

    let n: usize = lines.next().unwrap().unwrap().trim().parse().unwrap();
    let a: Vec<i32> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();

    let max_a = *a.iter().max().unwrap();
    let offset = max_a as usize;

    // dp[b + offset][m] の形で管理
    let mut dp: Vec<HashMap<i32, i64>> = vec![HashMap::new(); 2 * offset + 1];

    let mut answer: i64 = 0;

    for (i, &val) in a.iter().enumerate() {
        let i0 = (i + 1) as i32;

        // answer 計算
        let mut b = -val + i0;
        let mut m = 1;
        while b <= max_a {
            let index = (b + offset as i32) as usize;
            if let Some(&count) = dp[index].get(&m) {
                answer += count;
            }
            b += i0;
            m += 1;
        }

        // dp 更新
        let mut b = val - i0;
        let mut m = 1;
        while b >= -max_a {
            let index = (b + offset as i32) as usize;
            *dp[index].entry(m).or_insert(0) += 1;
            b -= i0;
            m += 1;
        }
    }

    println!("{}", answer);
}
0