제출 #487100

#제출 시각아이디문제언어결과실행 시간메모리
487100stefantagaSkyscraper (JOI16_skyscraper)C++14
20 / 100
112 ms19196 KiB
#include <bits/stdc++.h> #define MOD 1000000007 using namespace std; int v[105]; int din[105][105][1005][2][2],n,l,i,j,sum,S,F; int main() { ios_base :: sync_with_stdio(false); cin.tie(0); #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>n>>l; for (i=1;i<=n;i++) { cin>>v[i]; } sort (v+1,v+n+1); /// starile initiale din[1][0][0][1][1] = din[1][0][0][0][1] = din[1][0][0][1][0] = din[1][0][0][0][0] = 1; for (i=1;i<n;i++) { for (j=0;j<=n;j++) { for (sum=0;sum<=l;sum++) { for (S=0;S<=1;S++) { for (F=0;F<=1;F++) { int nou_sum=sum+(v[i+1]-v[i])*(2*j+F+S); if (din[i][j][sum][S][F]==0) { continue; } if (nou_sum>l) { continue; } if (j-1>=0) { din[i+1][j-1][nou_sum][S][F]=(din[i+1][j-1][nou_sum][S][F]+(1LL*din[i][j][sum][S][F]*j)%MOD)%MOD; } din[i+1][j][nou_sum][S][F]=(din[i+1][j][nou_sum][S][F]+(din[i][j][sum][S][F]*j*2)%MOD)%MOD; din[i+1][j+1][nou_sum][S][F]=(din[i+1][j+1][nou_sum][S][F]+(din[i][j][sum][S][F]*j)%MOD)%MOD; if (S==1) { din[i+1][j+1][nou_sum][0][F]=(din[i+1][j+1][nou_sum][0][F]+din[i][j][sum][S][F])%MOD; din[i+1][j+1][nou_sum][1][F]=(din[i+1][j+1][nou_sum][1][F]+din[i][j][sum][S][F])%MOD; din[i+1][j][nou_sum][0][F]=(din[i+1][j][nou_sum][0][F]+din[i][j][sum][S][F])%MOD; din[i+1][j][nou_sum][1][F]=(din[i+1][j][nou_sum][1][F]+din[i][j][sum][S][F])%MOD; } if (F==1) { din[i+1][j+1][nou_sum][S][0]=(din[i+1][j+1][nou_sum][S][0]+din[i][j][sum][S][F])%MOD; din[i+1][j+1][nou_sum][S][1]=(din[i+1][j+1][nou_sum][S][1]+din[i][j][sum][S][F])%MOD; din[i+1][j][nou_sum][S][0]=(din[i+1][j][nou_sum][S][0]+din[i][j][sum][S][F])%MOD; din[i+1][j][nou_sum][S][1]=(din[i+1][j][nou_sum][S][1]+din[i][j][sum][S][F])%MOD; } } } } } } long long solfin=0; for (sum=0;sum<=l;sum++) { solfin=(solfin+din[n][0][sum][0][0])%MOD; } cout<<solfin; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...