제출 #204195

#제출 시각아이디문제언어결과실행 시간메모리
204195amoo_safarSkyscraper (JOI16_skyscraper)C++14
100 / 100
121 ms16360 KiB
#include <bits/stdc++.h> #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef long long ll; typedef long double ld; typedef string str; typedef pair<ll, ll> pll; const ll Mod = 1000000007LL; const int N = 1e2 + 10; const int L = 1e3 + 10; const ll Inf = 2242545357980376863LL; const ll Log = 30; int n, l, a[N], ps[N]; int mul(int a, int b){ return (1ll * a * b) % Mod; } int mn[N][L][2][2]; int dp[N][N][L][2][2]; int Get(int l, int r){ return ps[max(0, r)] - ps[max(0, l)]; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> l; if(n == 1) return cout << "1\n", 0; for(int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); for(int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i - 1]; for(int i = 1; i <= n; i++){ for(int j = 1; j <= i; j++){ int p = n - i; mn[i][j][0][0] = 2 * Get(p - (j-1), p) + Get(p - (j+1), p - (j-1)); mn[i][j][0][1] = 2 * Get(p - (j-1), p) + Get(p - j, p - (j-1)); mn[i][j][1][0] = 2 * Get(p - (j-1), p) + Get(p - j, p - (j-1)); mn[i][j][1][1] = 2 * Get(p - (j-1), p); } } reverse(a, a + n); dp[1][1][ 2*a[0] - mn[1][1][0][0] ][0][0] = 1; dp[1][1][ a[0] - mn[1][1][1][0] ][1][0] = 1; dp[1][1][ a[0] - mn[1][1][0][1] ][0][1] = 1; int C, nC, X, P; for(int i = 1; i < n; i++){ X = a[i]; for(int j = 1; j <= i; j++){ for(int c = 0; c <= l; c++){ for(int b1 = 0; b1 < 2; b1++){ for(int b2 = 0; b2 < 2; b2++){ if(!dp[i][j][c][b1][b2]) continue; C = c + mn[i][j][b1][b2]; if(!b1){ nC = C + X - mn[i + 1][j + 1][1][b2]; if(0 <= nC && nC <= l) (dp[i + 1][j + 1][nC][1][b2] += dp[i][j][c][b1][b2]) %= Mod; nC = C - X - mn[i + 1][j][1][b2]; if(0 <= nC && nC <= l) (dp[i + 1][j][nC][1][b2] += dp[i][j][c][b1][b2]) %= Mod; } if(!b2){ nC = C + X - mn[i + 1][j + 1][b1][1]; if(0 <= nC && nC <= l) (dp[i + 1][j + 1][nC][b1][1] += dp[i][j][c][b1][b2]) %= Mod; nC = C - X - mn[i + 1][j][b1][1]; if(0 <= nC && nC <= l) (dp[i + 1][j][nC][b1][1] += dp[i][j][c][b1][b2]) %= Mod; } P = 2 * j - b1 - b2; nC = C - mn[i + 1][j][b1][b2]; if(0 <= nC && nC <= l) (dp[i + 1][j][nC][b1][b2] += mul(P, dp[i][j][c][b1][b2]) ) %= Mod; P = j + 1 - b1 - b2; nC = C + 2*X - mn[i + 1][j + 1][b1][b2]; if(0 <= nC && nC <= l) (dp[i + 1][j + 1][nC][b1][b2] += mul(P, dp[i][j][c][b1][b2]) ) %= Mod; P = j - 1; nC = C - 2*X - mn[i + 1][j - 1][b1][b2]; if(0 <= nC && nC <= l) (dp[i + 1][j - 1][nC][b1][b2] += mul(P, dp[i][j][c][b1][b2]) ) %= Mod; } } } } } int ans = 0; for(int i = 0; i <= l; i++){ ans = (ans + dp[n][1][i][1][1]) % Mod; } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...