Submission #607301

#TimeUsernameProblemLanguageResultExecution timeMemory
607301kawaiiSkyscraper (JOI16_skyscraper)C++14
15 / 100
2 ms1364 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second int t, n, l, m, k, a[1000005], dp[105][105][1005][3], mod = 1e9 + 7; string s; mt19937_64 rng; int mul(int x, int y){ if(y == 0) return 1; int ans = mul(x, y / 2); if(y % 2 == 0) return (ans * ans) % mod; else return (((ans * ans) % mod) * x) % mod; } void solve(){ sort(a + 1, a + n + 1); dp[0][0][0][0] = 1; for(int i = 1; i <= n; i++){ // for each i, set some ? to a[i] and calculate the sum abs for(int j = 1; j <= n; j++){ int diff = a[i] - a[i - 1], upd = 0; for(int sum = 0; sum <= l; sum++){ for(int k = 0; k <= 2; k++){ if(k >= 1){ // add an endpoint to front or back // before add an endpoint there are k - 1 endpoints // because there are j - 1 component before add a point -> need to add (j - 1) * 2 (OSU) upd = diff * ((j - 1) * 2 - (k - 1)); // create new component if(sum >= upd) dp[i][j][sum][k] = (dp[i][j][sum][k] + (2 - (k - 1)) * dp[i - 1][j - 1][sum - upd][k - 1]) % mod; // Similarly to (OSU) -> need to add j * 2 upd = diff * (j * 2 - (k - 1)); // add at the begin or end of an exist component if(sum >= upd) dp[i][j][sum][k] = (dp[i][j][sum][k] + (2 - (k - 1)) * dp[i - 1][j][sum - upd][k - 1]) % mod; } // add a point to somewhere different // because there are j component after add a point -> need to -1, 0, +1 in different case upd = diff * ((j - 1) * 2 - k); // create new component if(sum >= upd) dp[i][j][sum][k] = (dp[i][j][sum][k] + ((j - 1) + 1 - k) * dp[i - 1][j - 1][sum - upd][k]) % mod; upd = diff * ((j + 0) * 2 - k); // add at the begin or end of an exist component if(sum >= upd) dp[i][j][sum][k] = (dp[i][j][sum][k] + ((j + 0) * 2 - k) * dp[i - 1][j][sum - upd][k]) % mod; upd = diff * ((j + 1) * 2 - k); // merge two component if(sum >= upd) dp[i][j][sum][k] = (dp[i][j][sum][k] + ((j + 1) - 1) * dp[i - 1][j + 1][sum - upd][k]) % mod; } } } } int ans = 0; for(int i = 0; i <= l; i++) ans = (ans + dp[n][1][i][2]) % mod; cout << ans; } signed main(){ ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr); rng.seed((int)main ^ time(0)); #ifdef Kawaii auto starttime = chrono::high_resolution_clock::now(); #endif cin >> n >> l; for(int i = 1; i <= n; i++) cin >> a[i]; solve(); #ifdef Kawaii auto endtime = chrono::high_resolution_clock::now(); auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count(); cout << "\n=====" << "\nUsed: " << duration << " ms\n"; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...