Submission #1079311

#TimeUsernameProblemLanguageResultExecution timeMemory
1079311alexander707070Skyscraper (JOI16_skyscraper)C++14
0 / 100
569 ms2656 KiB
#include<bits/stdc++.h> #define MAXN 107 #define MAXS 207 using namespace std; const long long mod=1e9+7; int n,s,a[MAXN],ans; long long dp[MAXN][MAXN/2+5][MAXS][3][3]; long long dp2[MAXN][MAXN/2+5][MAXS][3][3]; long long even(int pos,int bal,int sum,int l,int r){ long long free=2*(bal-5)+(-(l==1)-(r==1)) - (-(l==2)-(r==2)); if(free<0)return 0; if(pos==n+1 and bal==5 and l+r==3 and sum-100<=s and free==0){ return 1; }else if(pos==n+1)return 0; if(free==0 and pos!=1)return 0; if(dp[pos][bal][sum][l][r]>0)return dp[pos][bal][sum][l][r]; dp[pos][bal][sum][l][r]+=even(pos+1,bal,sum,l,r)*free; if(l==0){ if(r!=1)dp[pos][bal][sum][l][r]+=even(pos+1,bal+1,sum-a[pos],1,r); if(r!=2)dp[pos][bal][sum][l][r]+=even(pos+1,bal-1,sum+a[pos],2,r); } if(r==0){ if(l!=1)dp[pos][bal][sum][l][r]+=even(pos+1,bal+1,sum-a[pos],l,1); if(l!=2)dp[pos][bal][sum][l][r]+=even(pos+1,bal-1,sum+a[pos],l,2); } long long mult=bal-5+1-(l==1)-(r==1); long long mult2=bal-5-1+(l==2)+(r==2); dp[pos][bal][sum][l][r]+=even(pos+1,bal+1,sum-2*a[pos],l,r)*mult; dp[pos][bal][sum][l][r]+=even(pos+1,bal-1,sum+2*a[pos],l,r)*mult2; dp[pos][bal][sum][l][r]%=mod; return dp[pos][bal][sum][l][r]; } long long odd(int pos,int bal,int sum,int l,int r){ long long free=2*(bal-5)+(-(l==1)-(r==1)) - (-(l==2)-(r==2)); if(free<0)return 0; if(pos==n+1 and (bal==4 or bal==6) and l==r and l!=0 and sum-100<=s and free==0){ return 1; }else if(pos==n+1)return 0; if(free==0 and pos!=1)return 0; if(dp2[pos][bal][sum][l][r]>0)return dp2[pos][bal][sum][l][r]; dp2[pos][bal][sum][l][r]+=odd(pos+1,bal,sum,l,r)*free; if(l==0){ if(r!=2)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal+1,sum-a[pos],1,r); if(r!=1)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal-1,sum+a[pos],2,r); } if(r==0){ if(l!=2)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal+1,sum-a[pos],l,1); if(l!=1)dp2[pos][bal][sum][l][r]+=odd(pos+1,bal-1,sum+a[pos],l,2); } long long mult=bal-5+1-(l==1)-(r==1); long long mult2=bal-5-1+(l==2)+(r==2); dp2[pos][bal][sum][l][r]+=odd(pos+1,bal+1,sum-2*a[pos],l,r)*mult; dp2[pos][bal][sum][l][r]+=odd(pos+1,bal-1,sum+2*a[pos],l,r)*mult2; dp2[pos][bal][sum][l][r]%=mod; return dp2[pos][bal][sum][l][r]; } void calc_even(){ ans+=even(1,5,100,0,0); } void calc_odd(){ ans+=odd(1,5,100,0,0); } int main(){ cin>>n>>s; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+n+1); calc_even(); calc_odd(); cout<<ans%mod<<"\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...