結果
問題 | No.1238 選抜クラス |
ユーザー |
|
提出日時 | 2020-11-25 13:47:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 875 ms / 2,000 ms |
コード長 | 2,380 bytes |
コンパイル時間 | 1,024 ms |
コンパイル使用メモリ | 103,948 KB |
最終ジャッジ日時 | 2025-01-16 05:37:26 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#include <string>#include <utility>#include <set>#include <map>#include <cmath>#include <queue>#include <cstdio>#include <limits>#define rep(i,n) for(int i = 0; i < n; ++i)#define rep1(i,n) for(int i = 1; i <= n; ++i)using namespace std;template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }template<class T> inline int sz(T &a) { return a.size(); }using ll = long long; using ld = long double;using pi = pair<int,int>; using pl = pair<ll,ll>;using vi = vector<int>; using vvi = vector<vi>;using vl = vector<ll>; using vvl = vector<vl>;const int inf = numeric_limits<int>::max();const ll infll = numeric_limits<ll>::max();// Modint// modint<MOD> で宣言template<ll MOD>struct modint{ll x;ll mod = MOD;modint(ll x=0):x(x%MOD){}modint& operator+=(const modint a){if((x+=a.x)>=MOD) x-=MOD;return *this;}modint& operator-=(const modint a){if((x += MOD-a.x)>=MOD) x-=MOD;return *this;}modint& operator*=(const modint a){(x*=a.x)%=MOD;return *this;}modint operator+(const modint a) const{modint res(*this);return res+=a;}modint operator-(const modint a) const{modint res(*this);return res-=a;}modint operator*(const modint a) const{modint res(*this);return res*=a;}modint pow(ll t) const{if(!t) return 1;modint a = pow(t>>1);a*=a;if(t&1) a*=*this;return a;}//for prime modmodint inv() const{return pow(MOD-2);}modint& operator/=(const modint a){return (*this) *= a.inv();}modint operator/(const modint a) const{modint res(*this);return res/=a;}};using mint = modint<1000000007>;int main(){int n,k; cin >> n >> k;vi a(n);rep(i,n) cin >> a[i];vector<vector<mint>> dp1(n+1, vector<mint>(10001));dp1[0][0].x = 1;rep(c,n) {vector<vector<mint>> dp2(n+1, vector<mint>(10001));rep(i,n) {rep(j,10001) {if(j + a[c] <= 10000) {dp2[i+1][j+a[c]] += dp1[i][j];}dp2[i][j] += dp1[i][j];}}swap(dp1, dp2);}mint res;rep1(i,n) {rep(j,10001) {if(j / i >= k) res += dp1[i][j];}}cout << res.x << "\n";return 0;}