제출 #94599

#제출 시각아이디문제언어결과실행 시간메모리
94599Bliss_of_comprehensionSkyscraper (JOI16_skyscraper)C++14
100 / 100
900 ms316924 KiB
#include <bits/stdc++.h> #define mod 1000000007 using namespace std; typedef long long ll; ll dp[105][105][1005][2][2]={}; int main(){ int n,l; cin >> n >> l; vector <int> a(n); for(int i=0;i<n;i++){ cin >> a[i]; } if(n==1){ cout << 1 << endl; return 0; } sort(a.begin(),a.end()); dp[0][0][0][0][0]=1; ll ans=0; for(int i=0;i<n;i++){ if(i==n-1){ for(int k=0;k<=l;k++){ for(int iss=0;iss<2;iss++){ for(int ise=0;ise<2;ise++){ dp[i][0][k][iss][ise]%=mod; if(iss+ise>0) ans=(ans+dp[i][0][k][iss][ise])%mod; } } } continue; } for(int j=0;j<=n;j++){ for(int k=0;k<=l;k++){ for(int iss=0;iss<2;iss++){ for(int ise=0;ise<2;ise++){ // if(i==2){ // cout << i << " " << j << " " << k << " " << iss << " " << ise << " " << dp[i][j][k][iss][ise] << endl; // } ll &cur = dp[i][j][k][iss][ise]; assert(cur>=0); cur%=mod; int diff = a[i+1]-a[i]; int nl=k+(a[i+1]-a[i])*(2*j+iss+ise); if(j){ if(nl-2*diff>l){ continue; } if(iss){ dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j; dp[i+1][j-1][nl-2*diff][iss][ise]%=mod; } if(ise){ dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j; dp[i+1][j-1][nl-2*diff][iss][ise]%=mod; } if(j>1){ dp[i+1][j-1][nl-2*diff][iss][ise]+=cur*j*(j-1); dp[i+1][j-1][nl-2*diff][iss][ise]%=mod; } if(nl-diff>l){ continue; } if(!iss){ dp[i+1][j-1][nl-diff][1][ise]+=cur*j; dp[i+1][j-1][nl-diff][1][ise]%=mod; } if(!ise){ dp[i+1][j-1][nl-diff][iss][1]+=cur*j; dp[i+1][j-1][nl-diff][iss][1]%=mod; } } if(nl>l){ continue; } if(iss){ dp[i+1][j][nl][iss][ise]+=cur; dp[i+1][j][nl][iss][ise]%=mod; } if(ise){ dp[i+1][j][nl][iss][ise]+=cur; dp[i+1][j][nl][iss][ise]%=mod; } if(j){ dp[i+1][j][nl][iss][ise]+=(2*j)*cur; dp[i+1][j][nl][iss][ise]%=mod; } if(nl+diff>l){ continue; } if(!iss){ dp[i+1][j][nl+diff][1][ise]+=cur; dp[i+1][j][nl+diff][1][ise]%=mod; } if(!ise){ dp[i+1][j][nl+diff][iss][1]+=cur; dp[i+1][j][nl+diff][iss][1]%=mod; } if(nl+2*diff>l){ continue; } dp[i+1][j+1][nl+2*diff][iss][ise]+=cur; dp[i+1][j+1][nl+2*diff][iss][ise]%=mod; } } } } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...