Submission #1042326

#TimeUsernameProblemLanguageResultExecution timeMemory
10423261L1YASkyscraper (JOI16_skyscraper)C++17
100 / 100
63 ms5636 KiB
//1L1YA #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3,unrool-loops") //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; #define Pb push_back #define F first #define S second #define endl '\n' #define sep ' ' #define all(x) x.begin(),x.end() #define al(x,n) x+1,x+n+1 #define SZ(x) ((int)x.size()) #define lc (id<<1) #define rc (lc|1) #define mid (l+r>>1) #define dokme(x) cout << x << endl, exit(0) #define sik(x) cout << x << endl;continue; #define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define FileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll oo=1e18; const int mod=1e9+7; const int inf=1e9+111; const int N=111; const int M=1011; const int lg=23; ll n,m,a[N],dp[M][N][3],DP[M][N][3]; int main(){ FastIO cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; if(n==1) dokme(1); sort(al(a,n)); DP[0][0][0]=1; a[n+1]=1e5; for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++) for(int k=1;k<=i;k++) for(int c=0;c<3;c++){ int p=2*k-c,w=j-p*(a[i+1]-a[i]); dp[j][k][c]=0; if(w<0) continue; dp[j][k][c]=(DP[w][k-1][c]*(k-c)+DP[w][k][c]*p+DP[w][k+1][c]*k)%mod; if(c) dp[j][k][c]=(dp[j][k][c]+DP[w][k-1][c-1]*(3-c)+DP[w][k][c-1]*(3-c))%mod; } for(int j=0;j<=m;j++) for(int k=0;k<=i;k++) for(int c=0;c<3;c++) DP[j][k][c]=dp[j][k][c]; } ll ans=0; for(int i=0;i<=m;i++) ans=(ans+dp[i][1][2])%mod; cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...