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
AC × 2
AC × 36
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