結果
問題 | No.1238 選抜クラス |
ユーザー |
![]() |
提出日時 | 2020-09-25 21:48:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 821 bytes |
コンパイル時間 | 2,434 ms |
コンパイル使用メモリ | 197,788 KB |
最終ジャッジ日時 | 2025-01-14 20:45:54 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { constexpr int64_t mod = 1000000007; int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; a[i] -= k; } vector<vector<int64_t>> dp(n + 1, vector<int64_t>(20001)); dp[0][10000] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j <= 20000; j++) { dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod; int j_next = j + a[i]; if (0 <= j_next and j_next <= 20000) { dp[i + 1][j_next] += dp[i][j]; dp[i + 1][j_next] %= mod; } } } int64_t ans = mod - 1; for (int i = 10000; i <= 20000; i++) { ans += dp[n][i]; ans %= mod; } cout << ans << endl; }