Submission #10185247
Source Code Expand
#include<bits/stdc++.h> #define pb push_back #define mp make_pair #define taskname "A" using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; const int maxn = 2e5 + 5; const int mod = 1e9 + 7; int dp[2][101][501]; int n , x; vector<int> val; void add(int & x , ll y){ x += y % mod; if(x >= mod)x -= mod; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } cin >> n >> x; val.resize(n); for(auto & c : val)cin >> c; sort(val.begin(),val.end(),greater<int>()); bool bit = 0;dp[0][0][0] = 1; for(auto & l : val){ for(int i = 0 ; i <= n ; ++i){ for(int j = 0 ; j <= x ; ++j){ if(dp[bit][i][j] > 0){ if(j + l <= x)add(dp[!bit][i + 1][j + l],(ll)dp[bit][i][j] * (i + 1)); if(i >= 1){ add(dp[!bit][i][j] , (ll)dp[bit][i][j] * (j - i * (l - 1))); for(int k = 1 ; k <= l && k + j <= x ; ++k){ add(dp[!bit][i][j+k],(ll)dp[bit][i][j]*i*2); if(i >= 2){ add(dp[!bit][i-1][j+k],(ll)dp[bit][i][j]*(l-k+1)*(i-1)); } } } dp[bit][i][j] = 0; } } } bit ^= 1; } cout << dp[bit][1][x]; }
Submission Info
Submission Time | |
---|---|
Task | E - Span Covering |
User | thanhqt2002 |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 1584 Byte |
Status | AC |
Exec Time | 131 ms |
Memory | 640 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:27:37: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result] freopen(taskname".INP", "r",stdin); ^ ./Main.cpp:28:38: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result] freopen(taskname".OUT", "w",stdout); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1100 / 1100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01, sample_02 |
All | fact_01, fact_02, max2_01, max2_02, max2_03, max2_04, max2_05, max2_06, max2_07, max2_08, max2_09, max2_10, max_01, max_02, max_03, max_04, max_05, max_06, max_07, max_08, max_09, max_10, random_01, random_02, random_03, random_04, random_05, sample_01, sample_02, small_01, small_02, small_03, small_04, small_05, zero_01, zero_02 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
fact_01 | AC | 17 ms | 640 KB |
fact_02 | AC | 31 ms | 640 KB |
max2_01 | AC | 92 ms | 384 KB |
max2_02 | AC | 91 ms | 384 KB |
max2_03 | AC | 120 ms | 512 KB |
max2_04 | AC | 115 ms | 512 KB |
max2_05 | AC | 121 ms | 512 KB |
max2_06 | AC | 117 ms | 512 KB |
max2_07 | AC | 115 ms | 384 KB |
max2_08 | AC | 117 ms | 384 KB |
max2_09 | AC | 94 ms | 384 KB |
max2_10 | AC | 93 ms | 384 KB |
max_01 | AC | 7 ms | 256 KB |
max_02 | AC | 6 ms | 256 KB |
max_03 | AC | 120 ms | 512 KB |
max_04 | AC | 120 ms | 512 KB |
max_05 | AC | 131 ms | 256 KB |
max_06 | AC | 131 ms | 256 KB |
max_07 | AC | 108 ms | 256 KB |
max_08 | AC | 108 ms | 256 KB |
max_09 | AC | 91 ms | 256 KB |
max_10 | AC | 91 ms | 256 KB |
random_01 | AC | 2 ms | 256 KB |
random_02 | AC | 2 ms | 256 KB |
random_03 | AC | 3 ms | 256 KB |
random_04 | AC | 2 ms | 256 KB |
random_05 | AC | 1 ms | 256 KB |
sample_01 | AC | 1 ms | 256 KB |
sample_02 | AC | 2 ms | 256 KB |
small_01 | AC | 1 ms | 256 KB |
small_02 | AC | 1 ms | 256 KB |
small_03 | AC | 1 ms | 256 KB |
small_04 | AC | 1 ms | 256 KB |
small_05 | AC | 1 ms | 256 KB |
zero_01 | AC | 25 ms | 640 KB |
zero_02 | AC | 27 ms | 640 KB |