제출 #681643

#제출 시각아이디문제언어결과실행 시간메모리
681643vjudge1Skyscraper (JOI16_skyscraper)C++17
100 / 100
1556 ms247820 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; #define ll long long #define pii pair<ll,ll> #define pll pair<ll,ll> #define vi vector<int> #define vll vector<long long> #define vpii vector<pii > #define Graph vector<vector<int> > #define WGraph vector<vector<pii>> #define read freopen("input.txt","r",stdin) #define write freopen("output.txt","w",stdout) #define mp(a,b) make_pair(a,b) #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); #define bound(i,j,n,m) ((i)<n&&(j)<m&&(i)>=0&&(j)>=0) #define all(container) container.begin(),container.end() #define fi first #define se second #define pub push_back #define sqr(x) ((x)*(x)) #define LL_MAX 0x7fffffffffffffff #define getPos(i,j,m) ((i)*m+(j)) const ll mod=1000000007; const int offset=200001; int dp[2][102][offset+2005*2][3]; int a[101]; int suf[101]; void solvecases(int cse) { int n,l; cin>>n>>l; for(int i=0;i<n;++i) cin>>a[i]; sort(a,a+n); for(int i=1;i<n;++i) a[i]=a[i]-a[0]; a[0]=0; for(int i=n-1;i>=0;--i) suf[i]=(suf[i+1]+a[i]); // for(int i=0;i<n;++i) // cout<<a[i]<<' '; // cout<<'\n'; dp[0][1][0+offset][0]=1; dp[0][1][0+offset][1]=2; dp[0][1][0+offset][2]=1; int cur=1; int sum=0; for(int i=1;i<n;++i) { for(int j=1;j<=i+1;++j){ for(int cost=-2*sum-2*a[i];cost<=2005;++cost){ for(int k=0;k<3;++k){ dp[cur][j][cost+offset][k]=0; } } } int prv=cur^1; for(int j=1;j<=min(i,n-i+1);++j) { for(int cost=max(-2*sum,-2*suf[i]);cost<=2005;++cost) { if(dp[prv][j][cost+offset][0]) { dp[cur][j+1][cost+offset-2*a[i]][0] =(dp[cur][j+1][cost+offset-2*a[i]][0]+ (ll)dp[prv][j][cost+offset][0]*(j+1))%mod; dp[cur][j+1][cost+offset-a[i]][1] =(dp[cur][j+1][cost+offset-a[i]][1]+ (ll)dp[prv][j][cost+offset][0]*(2))%mod; if(j>1&&cost+2*a[i]<=2005) { dp[cur][j-1][cost+offset+2*a[i]][0] =(dp[cur][j-1][cost+offset+2*a[i]][0]+ (ll)dp[prv][j][cost+offset][0]*(j-1))%mod; } dp[cur][j][cost+offset][0]= (dp[cur][j][cost+offset][0]+ (ll)dp[prv][j][cost+offset][0]*(2*j))%mod; if(cost+a[i]<=2005){ dp[cur][j][cost+offset+a[i]][1]= (dp[cur][j][cost+offset+a[i]][1]+ (ll)dp[prv][j][cost+offset][0]*2)%mod; } } if(dp[prv][j][cost+offset][1]) { dp[cur][j+1][cost+offset-2*a[i]][1] =(dp[cur][j+1][cost+offset-2*a[i]][1]+ (ll)dp[prv][j][cost+offset][1]*(j))%mod; dp[cur][j+1][cost+offset-a[i]][2] =(dp[cur][j+1][cost+offset-a[i]][2]+ dp[prv][j][cost+offset][1]); if(dp[cur][j+1][cost+offset-a[i]][2]>=mod) dp[cur][j+1][cost+offset-a[i]][2]-=mod; if(j>1&&cost+2*a[i]<=2005) { dp[cur][j-1][cost+offset+2*a[i]][1] =(dp[cur][j-1][cost+offset+2*a[i]][1]+ (ll)dp[prv][j][cost+offset][1]*(j-1))%mod; } dp[cur][j][cost+offset][1]= (dp[cur][j][cost+offset][1]+ (ll)dp[prv][j][cost+offset][1]*(2*j-1))%mod; if(cost+a[i]<=2005){ dp[cur][j][cost+offset+a[i]][2]= (dp[cur][j][cost+offset+a[i]][2]+ dp[prv][j][cost+offset][1]); if(dp[cur][j][cost+offset+a[i]][2]>=mod) dp[cur][j][cost+offset+a[i]][2]-=mod; } } if(dp[prv][j][cost+offset][2]) { if(j>1){ dp[cur][j+1][cost+offset-2*a[i]][2] =(dp[cur][j+1][cost+offset-2*a[i]][2]+ (ll)dp[prv][j][cost+offset][2]*(j-1))%mod; if(cost+2*a[i]<=2005){ dp[cur][j-1][cost+offset+2*a[i]][2]= (dp[cur][j-1][cost+offset+2*a[i]][2]+ (ll)dp[prv][j][cost+offset][2]*(j-1) )%mod; } dp[cur][j][cost+offset][2]= (dp[cur][j][cost+offset][2]+ (ll)dp[prv][j][cost+offset][2]*2*(j-1))%mod; } } } } cur^=1; sum+=a[i]; } cur^=1; ll ans=0; for(int i=0;i<=l;++i) ans+=dp[cur][1][i+offset][2]; // for(int i=-offset;i<0;++i) // assert(!dp[cur][1][i+offset][2]); ans%=mod; cout<<ans<<'\n'; } int main() { fastio; //build(100000); //brute(); int t=1; //cout<<fixed<<setprecision(2); //cin>>t; for(int i=1;i<=t;i++) { solvecases(i); //brute(i); } } /* 4 10 3 6 2 9 8 35 3 7 1 5 10 2 11 6 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...