제출 #730343

#제출 시각아이디문제언어결과실행 시간메모리
730343n0sk1llSkyscraper (JOI16_skyscraper)C++17
100 / 100
325 ms97728 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow int a[103]; int dp[103][103][1003][2][2]; int main() { FAST; int n,L; cin>>n>>L; fff(i,1,n) cin>>a[i]; sort(a+1,a+n+1),a[n+1]=mod; if (n==1) return cout<<1,0; dp[0][0][0][0][0]=1; fff(i,1,n) fff(j,1,n) fff(s,0,L) { li prevsum; prevsum=s-(li)(2*j)*(a[i+1]-a[i]); if (prevsum>=0) { (dp[i][j][s][0][0]+=dp[i-1][j-1][prevsum][0][0])%=mod; (dp[i][j][s][0][0]+=(li)2*j*dp[i-1][j][prevsum][0][0]%mod)%=mod; (dp[i][j][s][0][0]+=(li)j*(j+1)*dp[i-1][j+1][prevsum][0][0]%mod)%=mod; } prevsum=s-(li)(2*j-1)*(a[i+1]-a[i]); if (prevsum>=0) { (dp[i][j][s][0][1]+=dp[i-1][j-1][prevsum][0][1])%=mod; (dp[i][j][s][0][1]+=(li)(2*j-1)*dp[i-1][j][prevsum][0][1]%mod)%=mod; (dp[i][j][s][0][1]+=(li)(j*(j+1)-j)*dp[i-1][j+1][prevsum][0][1]%mod)%=mod; (dp[i][j][s][0][1]+=dp[i-1][j-1][prevsum][0][0])%=mod; (dp[i][j][s][0][1]+=(li)j*dp[i-1][j][prevsum][0][0]%mod)%=mod; } prevsum=s-(li)(2*j-1)*(a[i+1]-a[i]); if (prevsum>=0) { (dp[i][j][s][1][0]+=dp[i-1][j-1][prevsum][1][0])%=mod; (dp[i][j][s][1][0]+=(li)(2*j-1)*dp[i-1][j][prevsum][1][0]%mod)%=mod; (dp[i][j][s][1][0]+=(li)(j*(j+1)-j)*dp[i-1][j+1][prevsum][1][0]%mod)%=mod; (dp[i][j][s][1][0]+=dp[i-1][j-1][prevsum][0][0])%=mod; (dp[i][j][s][1][0]+=(li)j*dp[i-1][j][prevsum][0][0]%mod)%=mod; } prevsum=s-(li)(2*j-2)*(a[i+1]-a[i]); if (prevsum>=0) { (dp[i][j][s][1][1]+=dp[i-1][j-1][prevsum][1][1])%=mod; (dp[i][j][s][1][1]+=(li)(2*j-2)*dp[i-1][j][prevsum][1][1]%mod)%=mod; (dp[i][j][s][1][1]+=(li)(j*(j+1)-2*j)*dp[i-1][j+1][prevsum][1][1]%mod)%=mod; (dp[i][j][s][1][1]+=dp[i-1][j-1][prevsum][0][1])%=mod; (dp[i][j][s][1][1]+=dp[i-1][j-1][prevsum][1][0])%=mod; (dp[i][j][s][1][1]+=(li)(j-1)*dp[i-1][j][prevsum][0][1]%mod)%=mod; (dp[i][j][s][1][1]+=(li)(j-1)*dp[i-1][j][prevsum][1][0]%mod)%=mod; if (i==n && j==1) { (dp[i][j][s][1][1]+=dp[i-1][j+1][prevsum][1][1])%=mod; (dp[i][j][s][1][1]+=dp[i-1][j][prevsum][1][0])%=mod; (dp[i][j][s][1][1]+=dp[i-1][j][prevsum][0][1])%=mod; } } } int ans=0; fff(s,0,L) (ans+=dp[n][1][s][1][1])%=mod; cout<<ans<<"\n"; } //Note to self: Check for overflow
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...