제출 #122876

#제출 시각아이디문제언어결과실행 시간메모리
122876egorlifarSkyscraper (JOI16_skyscraper)C++17
100 / 100
250 ms19188 KiB
/* ЗАПУСКАЕМ ░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░ ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░ */ #include <iostream> #include <complex> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <numeric> #include <cstring> #include <ctime> #include <cstdlib> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <list> #include <cmath> #include <bitset> #include <cassert> #include <queue> #include <stack> #include <deque> using namespace std; template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; } template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; } template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; } template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; } template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; } template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; } template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; } #define sz(c) (int)(c).size() #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define left left228 #define right right228 #define next next228 #define rank rank228 #define prev prev228 #define y1 y1228 #define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin) #define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout) #define files(FILENAME) read(FILENAME), write(FILENAME) #define pb push_back const string FILENAME = "input"; const int MAXN = 101; const int Mod = 1000000007; int sum(int a, int b) { return (a + b >= Mod ? a + b - Mod: a + b); } int mul(int a, int b) { return (1LL * a * b) % Mod; } int n, m; int a[MAXN]; int dp[MAXN][MAXN][1001][2][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //read(FILENAME); cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } if (n == 1) { cout << 1 << endl; return 0; } sort(a, a + n); for (int i = n - 1; i >= 1; i--) { a[i] -= a[i - 1]; } a[0] = 0; dp[0][0][0][0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { for (int k = 0; k <= m; k++) { for (int l = 0; l < 2; l++) { for (int r = 0; r < 2; r++) { int cnt = dp[i][j][k][l][r]; if (!cnt) continue; int nk = k + a[i] * (2 * j - l - r); if (nk > m) { continue; } if (!l) { int mult = j - r; if (i == n - 1) { mult += r; } dp[i + 1][j][nk][1][r] = sum(dp[i + 1][j][nk][1][r], mul(mult, cnt)); dp[i + 1][j + 1][nk][1][r] = sum(dp[i + 1][j + 1][nk][1][r], cnt); } if (!r) { int mult = j - l; if (i == n - 1) { mult += l; } dp[i + 1][j][nk][l][1] = sum(dp[i + 1][j][nk][l][1], mul(mult, cnt)); dp[i + 1][j + 1][nk][l][1] = sum(dp[i + 1][j + 1][nk][l][1], cnt); } dp[i + 1][j][nk][l][r] = sum(dp[i + 1][j][nk][l][r], mul(cnt, 2 * j - l - r)); dp[i + 1][j + 1][nk][l][r] = sum(dp[i + 1][j + 1][nk][l][r], cnt); if (j > 1) { int mult = (j - l - r) * (j - 1); if (i == n - 1) { mult += (l & r); } dp[i + 1][j - 1][nk][l][r] = sum(dp[i + 1][j - 1][nk][l][r], mul(mult, cnt)); } } } } } } int ans = 0; for (int i = 0; i <= m; i++) { ans = sum(ans, dp[n][1][i][1][1]); } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...