Submission #1193917

#TimeUsernameProblemLanguageResultExecution timeMemory
1193917AMnuSkyscraper (JOI16_skyscraper)C++20
100 / 100
103 ms151352 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1e9+7, MAXN = 1e2+5, MAXL = 1e3+5; int N, L, A[MAXN], cost; ll dp[MAXN][MAXN][4][MAXL], sum; int main () { cin >> N >> L; for (int i=1;i<=N;i++) { cin >> A[i]; } sort(A+1,A+N+1); dp[1][1][0][0] = 1; dp[1][1][1][0] = 2; dp[1][1][2][0] = 1; for (int i=1;i<N;i++) { for (int j=1;j<=i;j++) { for (int k=0;k<3;k++) { cost = (A[i+1]-A[i])*(2*j-k); for (int l=cost;l<=L;l++) { dp[i+1][j-1][k][l] += dp[i][j][k][l-cost]*(j-1); dp[i+1][j][k][l] += dp[i][j][k][l-cost]*(2*j-k); dp[i+1][j][k+1][l] += dp[i][j][k][l-cost]*(2-k); dp[i+1][j+1][k][l] += dp[i][j][k][l-cost]*(j+1-k); dp[i+1][j+1][k+1][l] += dp[i][j][k][l-cost]*(2-k); dp[i+1][j-1][k][l] %= MOD; dp[i+1][j][k][l] %= MOD; dp[i+1][j][k+1][l] %= MOD; dp[i+1][j+1][k][l] %= MOD; dp[i+1][j+1][k+1][l] %= MOD; } } } } for (int i=0;i<=L;i++) { sum += dp[N][1][2][i]; sum %= MOD; } cout << sum << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...