oj.uz

Submission #745271

# Submission time Handle Problem Language Result Execution time Memory
745271 2023-05-19T16:55:01 Z sword060 Magneti (COCI21_magneti) C++17
0 / 110
 1000 ms 234372 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=10005,M=1e9+7;
long long add(long long a,long b){
	return (a+b)-(a+b>=M)*M;
}
long long mul(long long a,long long b){
	return (a*b)%M;
}
int x,k,a[N],ncr[N][N],fact[N];
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>x>>k;
  bool f=1;
  for(int i=1;i<=x;i++)cin>>a[i],f&=(a[i]==a[1]);
  fact[0]=1;
  for(int i=1;i<=x;i++)fact[i]=mul(fact[i-1],i);
  for(int i=0;i<=k;i++){
  	for(int j=0;j<=i;j++){
  		if(i==j||j==0)ncr[i][j]=1;
  		else ncr[i][j]=add(ncr[i-1][j],ncr[i-1][j-1]);
  	}
  }
  if(!f){
   long long sum=0,m=1,cnt=1;
   sort(a+1,a+x+1);
   for(int i=2;i<=x;i++){
   	if(a[i]==a[i-1])cnt++;
   	else{
   		m=mul(m,fact[cnt]);
   		cnt=1;
   	}
   }
   m=mul(m,fact[cnt]);
   do{
   	long long taken=1;
   	for(int i=2;i<=x;i++)
   		taken+=max(a[i-1],a[i]);
   	if(taken>k)continue;
   	sum=add(sum,mul(ncr[k][taken],m));
   }while(next_permutation(a+1,a+x+1));
   cout<<sum<<"\n";
  }else{
  	if(a[1]*x>k)cout<<0;
    else cout<<mul(ncr[k][k-a[1]*x],fact[x]);
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 234328 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 107 ms 167388 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 192 ms 234372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 1620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 234328 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 107 ms 167388 KB Output isn't correct
4 Halted 0 ms 0 KB -