Submission #685058

#TimeUsernameProblemLanguageResultExecution timeMemory
685058NeroZeinSkyscraper (JOI16_skyscraper)C++14
100 / 100
250 ms2732 KiB
/* * author: NeroZein * created: 23.01.2023 11:07:10 */ #include <bits/stdc++.h> using namespace std; #ifdef Nero #include "Deb.h" #else #define deb(...) #endif const int md = 1e9+7; inline void add(int& a, int b) { a += b; if(a >= md){ a -= md; } } inline int mul(int a, int b) { return (int)((long long) a * b % md); } signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } if(n == 1){ cout << 1 << '\n'; return 0; } sort(a.begin(), a.end()); vector<vector<array<int, 3>>>dp(n, vector<array<int, 3>>(m + 1)); //ncc, sum, used endpoints dp[1][0][0] = 1; dp[1][0][1] = 2; for (int i = 1; i < n; ++i) { vector<vector<array<int, 3>>>pd(n, vector<array<int, 3>>(m + 1)); for (int j = 1; j < n; ++j) { for(int k = 0; k <= m; ++k) { for(int e = 0; e < 3; ++e){ int diff = (2 * j - e) * (a[i] - a[i-1]); if(k + diff > m){ continue; } //merge two cc if(j > 1) { add(pd[j - 1][k + diff][e], mul(j - 1, dp[j][k][e])); } //create a cc if(j + 1 < n) { add(pd[j + 1][k + diff][e], mul(j + 1 - e, dp[j][k][e])); } //create a cc on the endpoints if(j + 1 < n && e < 2){ add(pd[j + 1][k + diff][e + 1], mul(2 - e, dp[j][k][e])); } //add to the left or right to an already existing component but not become an endpoint add(pd[j][k + diff][e], mul(2 * j - e, dp[j][k][e])); //add to the left or right to an already existing component but become an endpoint if(e < 2){ add(pd[j][k + diff][e + 1], mul(2 - e, dp[j][k][e])); } } } } swap(dp, pd); } int ans = 0; for(int i = 0; i <= m; ++i){ add(ans, dp[1][i][2]); } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...