結果
問題 | No.1238 選抜クラス |
ユーザー |
|
提出日時 | 2020-09-25 22:31:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 652 bytes |
コンパイル時間 | 1,635 ms |
コンパイル使用メモリ | 168,784 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 06:58:45 |
合計ジャッジ時間 | 2,900 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> #define int long long using namespace std; const int mod=1000000007; int dp[20100]; signed main(){ int N,K; cin>>N>>K; vector<int> A(N); for(int &i:A){ cin>>i; i-=K; } dp[10000]=1; for(int i=0;i<N;i++){ if(A[i]<0){ for(int j=-A[i];j<=20000;j++)dp[j+A[i]]=(dp[j+A[i]]+dp[j])%mod; }else if(A[i]>0){ for(int j=20000-A[i];j>=0;j--)dp[j+A[i]]=(dp[j+A[i]]+dp[j])%mod; }else{ for(int j=0;j<=20000;j++)dp[j]=dp[j]*2%mod; } } int ans=mod-1; for(int i=10000;i<=20000;i++)ans=(ans+dp[i])%mod; cout<<ans<<endl; }