Submission #1157206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157206		kerem	Magneti (COCI21_magneti)	C++20	110 / 110	137 ms	12616 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e18+1
#define N 10000
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed<<setprecision(0)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

const int mod=1000000007;
int comb[10055][55];
int dp[2][55][10005];
void init(){
	comb[0][0]=1;
	for(int i=1;i<=10050;i++){
		comb[i][0]=1;
		for(int j=1;j<=50;j++)
			comb[i][j]=(comb[i-1][j]+comb[i-1][j-1])%mod;
	}
}
void solve(){
	init();
	int n,l;
	cin >> n >> l;
	int a[n+1];
	for(int i=1;i<=n;i++)
		cin >> a[i];
	sort(a+1,a+n+1);
	int x=0;
	dp[x][1][1]=1;
	for(int i=2;i<=n;i++){
		x^=1;
		for(int j=1;j<=n;j++){
			for(int k=1;k<=l;k++){
				dp[x][j][k]=dp[x^1][j-1][k-1];
				if(k>=a[i]) dp[x][j][k]=(dp[x][j][k]+(dp[x^1][j][k-a[i]]*2*j)%mod)%mod;
				if(k>=2*a[i]-1) dp[x][j][k]=(dp[x][j][k]+(dp[x^1][j+1][k-2*a[i]+1]*j*(j+1))%mod)%mod;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=l;i++)
		ans=(ans+dp[x][1][i]*comb[l-i+n][n]%mod)%mod;
	cout << ans << endl;
}     
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	fast;
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50