#include <bits/stdc++.h>
using namespace std;
int a[101];
//number of cc,current cost , whether left side is chosen whether right is chosen
//index of element we are considering
const int MOD = 1e9+7;
int mult(int a,int b){
return a*1LL*b%MOD;
}
inline void add(int &a,int b){
a+=b;
if(a>=MOD)a-=MOD;
}
int dp[2][2][101][101][1001],n,L;
int solve(int lf,int rg,int i,int cnt,int cost){ //#total if we start from this state
if(cost>L || cnt<0)return 0;
if(dp[lf][rg][i][cnt][cost] != -1)return dp[lf][rg][i][cnt][cost];
if(i==n){ //base case
if(cnt==1 && lf && rg)return 1;
else return 0;
}
//once left and right border are made,no changes can be done to them :check
//no this fails
//new rule left and right border must start off as single cell
int d = a[i+1]-a[i];
dp[lf][rg][i][cnt][cost] = 0;
int nwcost = cost + (2*cnt - lf - rg) * d; //cost assuming every open end continues being open
//1)
//make single new cc
add(dp[lf][rg][i][cnt][cost],solve(lf,rg,i+1,cnt+1,nwcost + 2*d));
//make single new left cc
if(!lf)add(dp[lf][rg][i][cnt][cost],solve(1,rg,i+1,cnt+1,nwcost + d));
//make single new right cc
if(!rg)add(dp[lf][rg][i][cnt][cost],solve(lf,1,i+1,cnt+1,nwcost + d));
//2)
//connect to left side of smtg
if(cnt-lf)add(dp[lf][rg][i][cnt][cost],mult(cnt-lf,solve(lf,rg,i+1,cnt,nwcost)));
//connect to right side of smtg
if(cnt-rg)add(dp[lf][rg][i][cnt][cost],mult(cnt-rg,solve(lf,rg,i+1,cnt,nwcost)));
//make single left then connect smtg
if(!lf && cnt-rg)add(dp[lf][rg][i][cnt][cost],mult(cnt-rg,solve(1,rg,i+1,cnt,nwcost-d)));
//make single right then connect smtg
if(!rg && cnt-lf)add(dp[lf][rg][i][cnt][cost],mult(cnt-lf,solve(lf,1,i+1,cnt,nwcost-d)));
//3)
//merge ccs
int cc = cnt-lf-rg;
if(cc>=2)add(dp[lf][rg][i][cnt][cost],mult(cc*(cc+1)/2,solve(lf,rg,i+1,cnt-1,nwcost - 2*d)));
if(cc && lf)add(dp[lf][rg][i][cnt][cost],mult(cc,solve(lf,rg,i+1,cnt-1,nwcost - 2*d)));
if(cc && rg)add(dp[lf][rg][i][cnt][cost],mult(cc,solve(lf,rg,i+1,cnt-1,nwcost - 2*d)));
//merge left and right border
//only possible in enddgame
//4)
if(i==n-1){
if(lf && rg)add(dp[lf][rg][i][cnt][cost],solve(1,1,n,cnt-1,nwcost - 2*d));
if(lf && !rg)add(dp[lf][rg][i][cnt][cost],solve(1,1,n,cnt,nwcost)); //connect to left side
if(!lf && rg)add(dp[lf][rg][i][cnt][cost],solve(1,1,n,cnt,nwcost)); //connected to right side
}
cout<<dp[lf][rg][i][cnt][cost]<<'\n';
return dp[lf][rg][i][cnt][cost];
}
int main()
{
cin>>n>>L;
for(int i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
a[n] = a[n-1];
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=L;k++){
for(int mask=0;mask<=3;mask++){
dp[mask&1][mask/2][i][j][k] = -1;
}
}
}
}
cout<<solve(0,0,0,0,0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
