Submission #1079323

#TimeUsernameProblemLanguageResultExecution timeMemory
1079323alexander707070Skyscraper (JOI16_skyscraper)C++14
15 / 100
66 ms19148 KiB
#include<bits/stdc++.h> #define MAXN 107 #define MAXS 5007 using namespace std; const long long mod=1e9+7; int n,s,a[MAXN],ans; unordered_map<int,long long> dp[MAXN][MAXN/2+5][3][3]; unordered_map<int,long long> dp2[MAXN][MAXN/2+5][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<=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][l][r].find(sum)!=dp[pos][bal][l][r].end())return dp[pos][bal][l][r][sum]; long long curr=0; curr+=even(pos+1,bal,sum,l,r)*free; if(l==0){ if(r!=1)curr+=even(pos+1,bal+1,sum-a[pos],1,r); if(r!=2)curr+=even(pos+1,bal-1,sum+a[pos],2,r); } if(r==0){ if(l!=1)curr+=even(pos+1,bal+1,sum-a[pos],l,1); if(l!=2)curr+=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); curr+=even(pos+1,bal+1,sum-2*a[pos],l,r)*mult; curr+=even(pos+1,bal-1,sum+2*a[pos],l,r)*mult2; curr%=mod; dp[pos][bal][l][r][sum]=curr; return curr; } 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<=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][l][r].find(sum)!=dp2[pos][bal][l][r].end())return dp2[pos][bal][l][r][sum]; long long curr=0; curr+=odd(pos+1,bal,sum,l,r)*free; if(l==0){ if(r!=2)curr+=odd(pos+1,bal+1,sum-a[pos],1,r); if(r!=1)curr+=odd(pos+1,bal-1,sum+a[pos],2,r); } if(r==0){ if(l!=2)curr+=odd(pos+1,bal+1,sum-a[pos],l,1); if(l!=1)curr+=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); curr+=odd(pos+1,bal+1,sum-2*a[pos],l,r)*mult; curr+=odd(pos+1,bal-1,sum+2*a[pos],l,r)*mult2; curr%=mod; dp2[pos][bal][l][r][sum]=curr; return curr; } void calc_even(){ ans+=even(1,5,0,0,0); } void calc_odd(){ ans+=odd(1,5,0,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...