Submission #1224879

#TimeUsernameProblemLanguageResultExecution timeMemory
1224879MarwenElarbiSkyscraper (JOI16_skyscraper)C++20
15 / 100
1 ms840 KiB
#include <bits/stdc++.h> using namespace std; const int MOD=1e9+7; int n,l; long long dp[105][51][1005][3]; vector<int> tab(105); int main(void) { cin>>n>>l; tab.resize(n); for (int i = 0; i < n; ++i) { cin>>tab[i]; } sort(tab.begin(),tab.end()); dp[0][0][0][0]=1; for (int i = 1; i <= n; ++i) { for (int c = 1; c <= i; ++c) { for (int b = 0; b < 3; ++b) { for (int sum = 0; sum <= l; ++sum) { int oldsum=sum; if(i<n) oldsum-=(c*2-b)*(tab[i]-tab[i-1]); if(oldsum<0) continue; if(c+1<=i-1) dp[i][c][sum][b]+=dp[i-1][c+1][oldsum][b]*c; dp[i][c][sum][b]+=dp[i-1][c-1][oldsum][b]*(c-b); dp[i][c][sum][b]+=dp[i-1][c][oldsum][b]*(2*c-b); if(b>0) dp[i][c][sum][b]+=dp[i-1][c-1][oldsum][b-1]*(3-b); if(b>0) dp[i][c][sum][b]+=dp[i-1][c][oldsum][b-1]*(3-b); dp[i][c][sum][b]%=MOD; //cout <<i<<" "<<c<<" "<<sum<<" "<<b<<" "<<dp[i][c][sum][b]<<endl; } } } } long long ans=0; for (int i = 0; i <= l; ++i) { ans+=dp[n][1][i][2]; ans%=MOD; } cout <<ans<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...