結果
問題 | No.1238 選抜クラス |
ユーザー |
|
提出日時 | 2020-09-25 23:15:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 717 bytes |
コンパイル時間 | 1,776 ms |
コンパイル使用メモリ | 196,968 KB |
最終ジャッジ日時 | 2025-01-14 21:33:22 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long int; using lc = complex<double>; int main(void) { constexpr ll MOD = 1e9+7; constexpr double PI = acos(-1); cout << fixed << setprecision(32); cin.tie(0); ios::sync_with_stdio(false); ll n, k; cin >> n >> k; vector<ll> a(n); for(auto &e: a) cin >> e, e -= k; vector<ll> dp(30000); dp[15000] = 1; for(ll i=0; i<n; i++) { vector<ll> dq = dp; for(ll j=30000-1; j>=0; j--) { if(j-a[i]<30000&&j-a[i]>=0) (dp[j] += dq[j-a[i]]) %= MOD; } } ll r = 0; for(ll i=15000; i<30000; i++) (r += dp[i]) %= MOD; (r += (MOD - 1)) %= MOD; cout << r << endl; }