Submission #3455766


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

ll power(int k,int n,int M){
  if(n==0) return 1;
  if(n==1) return (ll)k;
  
  ll ret = power(k,n/2,M);
  
  ret=(ret*ret)%M;
  
  if(n%2==1) ret=(ret*k)%M;
  
  return ret;
}

/*Combination*/
int C(int n,int m,int M){
  if(n<m) return 0;
  if(m==0 || n==m) return 1;

  ll r = 1, t = 1;
  for(int i=0;i<m;i++) r = (r * (n-i))%M;
  for(int i=0;i<m;i++) t = (t * (i+1))%M;
  return r * power(t, mod-2, mod) % mod;
}

ll dp2[31][30*30+1];

ll fact[30*30+1], factr[30*30+1];


void init(){
  fact[0] = 1;
  for(int i=1;i<=30*30;i++) fact[i] = (fact[i-1] * i)%mod;
  for(int i=0;i<=30*30;i++) factr[i] = power(fact[i], mod-2, mod);  
}


int main(){
  int n, d, a[31], sum = 0;

  init();
  
  scanf("%d%d", &n, &d);

  for(int i=0;i<n;i++){
    scanf("%d", a+i);
    sum += a[i];
  }

  if(sum < d){
    puts("0");
    return 0;
  }

  dp2[0][0] = 1;
  
  for(int i=0;i<n;i++){
    for(int j=i;j>=0;j--){
      for(int k=0;k<=j*30;k++){
        for(int l=0;l<a[i];l++){
          ll add = dp2[j][k] * fact[k+l] % mod * factr[l] % mod * factr[k] % mod;
          dp2[j+1][k+l] = (dp2[j+1][k+l] + add) % mod;
        }
      }
    }
  }
  
  ll ans = 0;
  
  for(int i=0;i<n;i++){
    for(int j=0;j<=i*30;j++){
      if(d < j) continue;
      ll add = dp2[i][j] * C(d, j, mod) % mod * power(n-i, d-j, mod) % mod;
      if(i%2) add *= -1;
      ans = (ans + add + mod) % mod;
    }
  }
  
  cout << ans << endl;
  
  
  return 0;
}

Submission Info

Submission Time
Task D - 天下一ボディービルコンテスト
User goodbaton
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2123 Byte
Status WA
Exec Time 2 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &d);
                        ^
./Main.cpp:75:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", a+i);
                     ^

Judge Result

Set Name level1 level2 level3
Score / Max Score 0 / 40 0 / 100 0 / 140
Status
AC × 2
WA × 25
AC × 2
WA × 48
AC × 2
WA × 72
Set Name Test Cases
level1 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt
level2 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt, level2_max_0.txt, level2_maxrand_0.txt, level2_maxrand_1.txt, level2_maxrand_2.txt, level2_maxrand_3.txt, level2_maxrand_4.txt, level2_maxrand_5.txt, level2_maxrand_6.txt, level2_maxrand_7.txt, level2_maxrand_8.txt, level2_maxrand_9.txt, level2_min1_0.txt, level2_min2_0.txt, level2_rand_0.txt, level2_rand_1.txt, level2_rand_2.txt, level2_rand_3.txt, level2_rand_4.txt, level2_rand_5.txt, level2_rand_6.txt, level2_rand_7.txt, level2_rand_8.txt, level2_rand_9.txt
level3 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt, level2_max_0.txt, level2_maxrand_0.txt, level2_maxrand_1.txt, level2_maxrand_2.txt, level2_maxrand_3.txt, level2_maxrand_4.txt, level2_maxrand_5.txt, level2_maxrand_6.txt, level2_maxrand_7.txt, level2_maxrand_8.txt, level2_maxrand_9.txt, level2_min1_0.txt, level2_min2_0.txt, level2_rand_0.txt, level2_rand_1.txt, level2_rand_2.txt, level2_rand_3.txt, level2_rand_4.txt, level2_rand_5.txt, level2_rand_6.txt, level2_rand_7.txt, level2_rand_8.txt, level2_rand_9.txt, level3_max_0.txt, level3_maxrand_0.txt, level3_maxrand_1.txt, level3_maxrand_2.txt, level3_maxrand_3.txt, level3_maxrand_4.txt, level3_maxrand_5.txt, level3_maxrand_6.txt, level3_maxrand_7.txt, level3_maxrand_8.txt, level3_maxrand_9.txt, level3_min1_0.txt, level3_min2_0.txt, level3_rand_0.txt, level3_rand_1.txt, level3_rand_2.txt, level3_rand_3.txt, level3_rand_4.txt, level3_rand_5.txt, level3_rand_6.txt, level3_rand_7.txt, level3_rand_8.txt, level3_rand_9.txt, level3_sample3.txt
Case Name Status Exec Time Memory
level1_max_0.txt WA 2 ms 256 KB
level1_maxrand_0.txt WA 2 ms 256 KB
level1_maxrand_1.txt WA 2 ms 256 KB
level1_maxrand_2.txt WA 2 ms 256 KB
level1_maxrand_3.txt WA 2 ms 256 KB
level1_maxrand_4.txt WA 2 ms 256 KB
level1_maxrand_5.txt WA 2 ms 256 KB
level1_maxrand_6.txt WA 2 ms 256 KB
level1_maxrand_7.txt WA 2 ms 256 KB
level1_maxrand_8.txt WA 2 ms 256 KB
level1_maxrand_9.txt WA 2 ms 256 KB
level1_min1_0.txt WA 2 ms 256 KB
level1_min2_0.txt WA 2 ms 256 KB
level1_min3_0.txt WA 2 ms 256 KB
level1_min4_0.txt AC 2 ms 256 KB
level1_rand_0.txt WA 2 ms 256 KB
level1_rand_1.txt WA 2 ms 256 KB
level1_rand_2.txt WA 2 ms 256 KB
level1_rand_3.txt WA 2 ms 256 KB
level1_rand_4.txt WA 2 ms 256 KB
level1_rand_5.txt WA 2 ms 256 KB
level1_rand_6.txt WA 2 ms 256 KB
level1_rand_7.txt WA 2 ms 256 KB
level1_rand_8.txt WA 2 ms 256 KB
level1_rand_9.txt WA 2 ms 256 KB
level1_sample1.txt WA 2 ms 256 KB
level1_sample2.txt AC 2 ms 256 KB
level2_max_0.txt WA 2 ms 256 KB
level2_maxrand_0.txt WA 2 ms 256 KB
level2_maxrand_1.txt WA 2 ms 256 KB
level2_maxrand_2.txt WA 2 ms 256 KB
level2_maxrand_3.txt WA 2 ms 256 KB
level2_maxrand_4.txt WA 2 ms 256 KB
level2_maxrand_5.txt WA 2 ms 256 KB
level2_maxrand_6.txt WA 2 ms 256 KB
level2_maxrand_7.txt WA 2 ms 256 KB
level2_maxrand_8.txt WA 2 ms 256 KB
level2_maxrand_9.txt WA 2 ms 256 KB
level2_min1_0.txt WA 2 ms 256 KB
level2_min2_0.txt WA 2 ms 256 KB
level2_rand_0.txt WA 2 ms 256 KB
level2_rand_1.txt WA 2 ms 256 KB
level2_rand_2.txt WA 2 ms 256 KB
level2_rand_3.txt WA 2 ms 256 KB
level2_rand_4.txt WA 2 ms 256 KB
level2_rand_5.txt WA 2 ms 256 KB
level2_rand_6.txt WA 2 ms 256 KB
level2_rand_7.txt WA 2 ms 256 KB
level2_rand_8.txt WA 2 ms 256 KB
level2_rand_9.txt WA 2 ms 256 KB
level3_max_0.txt WA 2 ms 256 KB
level3_maxrand_0.txt WA 2 ms 256 KB
level3_maxrand_1.txt WA 2 ms 256 KB
level3_maxrand_2.txt WA 2 ms 256 KB
level3_maxrand_3.txt WA 2 ms 256 KB
level3_maxrand_4.txt WA 2 ms 256 KB
level3_maxrand_5.txt WA 2 ms 256 KB
level3_maxrand_6.txt WA 2 ms 256 KB
level3_maxrand_7.txt WA 2 ms 256 KB
level3_maxrand_8.txt WA 2 ms 256 KB
level3_maxrand_9.txt WA 2 ms 256 KB
level3_min1_0.txt WA 2 ms 256 KB
level3_min2_0.txt WA 2 ms 256 KB
level3_rand_0.txt WA 2 ms 256 KB
level3_rand_1.txt WA 2 ms 256 KB
level3_rand_2.txt WA 2 ms 256 KB
level3_rand_3.txt WA 2 ms 256 KB
level3_rand_4.txt WA 2 ms 256 KB
level3_rand_5.txt WA 2 ms 256 KB
level3_rand_6.txt WA 2 ms 256 KB
level3_rand_7.txt WA 2 ms 256 KB
level3_rand_8.txt WA 2 ms 256 KB
level3_rand_9.txt WA 2 ms 256 KB
level3_sample3.txt WA 2 ms 256 KB