oj.uz

답안 #867190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867190 2023-10-27T20:23:24 Z NotLinux Magneti (COCI21_magneti) C++17
50 / 110
 1000 ms 35676 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()


constexpr int MOD = (int) 1e9 + 7;

inline int add(int a,int b){
  if(a+b >= MOD)return a+b-MOD;
  else return a+b;
}

inline int mult(int a,int b){
  return (a*b)%MOD;
}

inline int fast(int a,int b){
  if(b==0) return 1;
  int res=fast(a,b/2);
  res=mult(res,res);
  if(b&1) res=mult(res,a);
  return res;
}

void solve(){

  int n,l;
  cin >> n >> l;
  
  vector<int> ar;

  int fact[10005];
  int inv_fact[10005];
  fact[0]=1;
  for(int i=1;i<10005;i++) fact[i]=mult(i,fact[i-1]);
  
  inv_fact[10004]=fast(fact[10004],MOD-2);

  for(int i=10003;i>=0;i--) inv_fact[i]=mult(inv_fact[i+1],i+1);

  for(int i=1;i<=n;i++){
    int a;
    cin >> a;
    ar.pb(a);
  }

  if(n==1){
    cout << l << endl;
    return;
  }

  sort(all(ar));
  reverse(all(ar));

  int dp[n+6][l+6][4];
  int ndp[n+6][l+6][4];
  
  memset(dp,0,sizeof(dp));
  memset(ndp,0,sizeof(ndp));

  dp[0][0][0]=1;

  for(int i=0;i<n;i++){

    // merge 
    for(int j=2;j<=n;j++){
       for(int x=0;x<l;x++){
         for(int fl=0;fl<=2;fl++){
           ndp[j-1][x+1][fl]=add(ndp[j-1][x+1][fl],mult(j-1,dp[j][x][fl]));
         }
       }
    }

    // extend
    for(int j=1;j<=n;j++){
       for(int x=0;x<=l;x++){
         for(int fl=0;fl<=2;fl++){
           if(x+ar[i]<=l) ndp[j][x+ar[i]][fl]=add(ndp[j][x+ar[i]][fl],mult(2*j-fl,dp[j][x][fl]));
           if(fl+1<=2 && x+1<=l) ndp[j][x+1][fl+1]=add(ndp[j][x+1][fl+1],mult(2-fl,dp[j][x][fl]));
         }
       }
    }
  
    // create1
    for(int j=0;j<n;j++){
      for(int x=0;x+2*ar[i]-1<=l;x++){
        for(int fl=0;fl<=2;fl++){
          ndp[j+1][x+2*ar[i]-1][fl]=add(ndp[j+1][x+2*ar[i]-1][fl],mult(j+1-fl,dp[j][x][fl]));
        }
      }
    }

    // create2
    for(int j=0;j<n;j++){
      for(int x=0;x+ar[i]<=l;x++){
        for(int fl=0;fl<2;fl++){
          ndp[j+1][x+ar[i]][fl+1]=add(ndp[j+1][x+ar[i]][fl+1],mult(2-fl,dp[j][x][fl]));
        }
      }
    }

    //swap values

    memset(dp,0,sizeof(dp));

    for(int j=0;j<=n;j++)
      for(int x=0;x<=l;x++)
        for(int fl=0;fl<=2;fl++)
          dp[j][x][fl]=ndp[j][x][fl];

    memset(ndp,0,sizeof(ndp));
  }
  
  int ans=0;
  for(int x=0;x<=l;x++){
    ans=add(ans,mult(mult(fact[n+l-x],mult(inv_fact[n],inv_fact[l-x])),dp[1][x][2]));
  }

  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1018 ms 35676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 10584 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 38 ms 10628 KB Output is correct
4 Correct 7 ms 5212 KB Output is correct
5 Correct 38 ms 10588 KB Output is correct
6 Correct 7 ms 3676 KB Output is correct
7 Correct 40 ms 10588 KB Output is correct
8 Correct 4 ms 1524 KB Output is correct
9 Correct 6 ms 4188 KB Output is correct
10 Correct 0 ms 604 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1292 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 10 ms 1292 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 9 ms 1112 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 11 ms 1116 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct

Subtask #4
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1018 ms 35676 KB Time limit exceeded
2 Halted 0 ms 0 KB -