• コンテスト (AtCoder Typical DP Contest A問題) https://atcoder.jp/contests/tdpc/tasks/tdpc_contest
  • https://atcoder.jp/contests/tdpc/submissions/40788672
  • 1 <= p_i <= 100 を N <= 100 個なのですべて 100 でも 10000 にしかならない
  • p_i についてひとつ前まででできる合計に p_i を加えたもの・加えないものをそれぞれ確認しても 1_000_000 程度なので間に合う

use proconio::input;

fn main() {
    input! {
        n: usize,
        p: [usize; n],
    }

    let mut dp = vec![false; 100 * 100 + 1];
    dp[0] = true;
    for p_i in p {
        let mut next = vec![false; 100 * 100 + 1];
        for j in 0..dp.len() {
            if !dp[j] {
                continue;
            }
            next[j + p_i] = true;
            next[j] = true;
        }
        dp = next;
    }
    let ans = dp.into_iter().filter(|b| *b).count();
    println!("{}", ans);
}

今日のコミット。

• tsukota 1 commit
  • Add messages for transaction edit to i18n mod
• rust-atcoder 1 commit
  • pastbook1 tdpc a