Submission #122644

#TimeUsernameProblemLanguageResultExecution timeMemory
122644ZwariowanyMarcinSkyscraper (JOI16_skyscraper)C++14
15 / 100
2 ms760 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pb push_back #define ld long double #define fi first #define se second #define ll long long #define ss(x) (int) x.size() #define mp make_pair #define FOR(i, n) for(int i = 1; n >= i; ++i) using namespace std; using namespace __gnu_pbds; const int nax = 105, mod = 1e9 + 7; int n, s; int a[nax]; int dp[nax][nax][1005][3]; void add(int &a, int b) { a += b; if(a >= mod) a -= mod; } int jazda(int x, int y) { int normal = x - y; int odp = normal * (normal - 1); odp += y * (x - 1); if(y == 2) odp -= 2; odp %= mod; return odp; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> s; for(int i = 1; i <= n; ++i) { cin >> a[i]; } sort(a + 1, a + n + 1); dp[0][0][0][0] = 1; for(int i = 0; i < n; ++i) { for(int j = 0; j <= n; ++j) { for(int sum = 0; sum <= s; ++sum) { for(int ile = 0; ile <= 2; ++ile) { if(dp[i][j][sum][ile] == 0) continue; int val = dp[i][j][sum][ile]; //5 cout << i << " " << j << " " << sum << " " << ile << " " << val << endl; // 1. dodaj 1 // cout << dp[2][0][9][1] << " 1" << endl; int dodatek = 2 * (j + 1) - ile; int nsum = sum + dodatek * (a[i + 2] - a[i + 1]); if(nsum <= s && i < n - 1) add(dp[i + 1][j + 1][nsum][ile], val); // 2. dodaj kraniec + 1 if(ile <= 1 && i < n - 1) { dodatek = 2 * (j + 1) - ile - 1; nsum = sum + dodatek * (a[i + 2] - a[i + 1]); if(nsum <= s) add(dp[i + 1][j + 1][nsum][ile + 1], (ll) val * (ile == 0 ? 2 : 1) % mod); } //cout << dp[2][0][9][1] << " 3" << endl; // 3. dodaj kraniec + 0 if(ile <= 1 && j >= 1 && j > ile) { dodatek = 2 * j - ile - 1; nsum = sum + dodatek * (a[i + 2] - a[i + 1]); // cout << i << " " << nsum << "AAA" << " " << dodatek << endl; if(nsum <= s) add(dp[i + 1][j][nsum][ile + 1], (ll) (j - ile) * val * (ile == 0 ? 2 : 1) % mod); } // cout << dp[2][0][9][1] << " 4" << endl; // 4. end if(i == n - 1 && ile == 2 && j == 2) { dodatek = 2 * (j - 1) - ile; nsum = sum; //cout << i << " " << nsum << "BBB" << endl; if(nsum <= s) add(dp[i + 1][j - 1][nsum][ile], val); } if(i == n - 1 && ile == 1 && j == 1) { nsum = sum; // cout << nsum << "a" << endl; add(dp[i + 1][j][nsum][2], val); } // cout << dp[2][0][9][1] << " 5" << endl; // 5. + 0 if(j >= 1 && i < n - 1) { dodatek = 2 * j - ile; nsum = sum + dodatek * (a[i + 2] - a[i + 1]); if(nsum <= s) add(dp[i + 1][j][nsum][ile], (ll) val * ((j - ile) * 2 + ile) % mod); } // cout << dp[2][0][9][1] << endl; // 6. polacz if(j >= 2 && j - ile > 0 && i < n - 1) { // cout << "CCC" << i << " " << j << " " << ile << endl; dodatek = 2 * (j - 1) - ile; nsum = sum + dodatek * (a[i + 2] - a[i + 1]); if(nsum <= s) add(dp[i + 1][j - 1][nsum][ile], (ll) val * (jazda(j, ile)) % mod); } // cout << dp[2][0][9][1] << endl; } } } } int ans = 0; for(int i = 0; i <= s; ++i) { // cout << dp[n][1][i][2] << endl; add(ans, dp[n][1][i][2]); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...