Submission #550126

#TimeUsernameProblemLanguageResultExecution timeMemory
550126theshadow_04Skyscraper (JOI16_skyscraper)C++14
15 / 100
280 ms269812 KiB
#include <bits/stdc++.h> #define Task "CF" #define MOD 1000000007 #define pb push_back using namespace std; const int maxn = 200005; int n, l; int a[maxn]; void Sub1() { vector<int> v; for(int i = 1; i <= n; ++i) v.pb(i); int ans = 0; do { long long res = 0; for(int i = 0; i < (int) v.size() - 1; ++ i) res += abs(a[v[i + 1]] - a[v[i]]); if(res <= l) ++ ans; if(ans > MOD) ans -= MOD; } while(next_permutation(v.begin(), v.end())); cout << ans << "\n"; } namespace Sub2 { long long dp[(1 << 14) + 5][20][105]; void solve() { memset(dp, 0, sizeof dp); for(int i = 0; i < n; ++ i) { dp[(1 << i)][i][0] = 1; } for(int mask = 0; mask < (1 << n); ++ mask) { for(int last = 0; last < n; ++ last) { for(int s = 0; s <= l; ++ s) { if(dp[mask][last][s] == 0 || !(mask >> last & 1)) continue; for(int nex = 0; nex < n; ++ nex) { if((mask >> nex & 1) || s + abs(a[last] - a[nex]) > l) continue; (dp[mask + (1 << nex)][nex][s + abs(a[last] - a[nex])] += dp[mask][last][s]) %= MOD; } } } } long long ans = 0; for(int last = 0; last < n; ++ last) { for(int s = 0; s <= l; ++ s) { (ans += dp[(1 << n) - 1][last][s]) %= MOD; } } cout << ans << "\n"; } } // connected component DP / USACE code namespace Full { long long dp[102][102][1002][3]; /* dp[i][j][k][l] : i - number of numbers placed j - number of connected components k - total sum currently (filling empty spaces with a_{i} (0-indexed) l - number of endpoints that are filled */ void solve() { sort(a + 1, a + n + 1); a[n + 1] = 10000; dp[0][0][0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { for (int k = 0; k <= l; k++) { for (int m = 0; m <= 2; m++) { int cost_diff = (2 * j - m) * (a[i + 1] - a[i]); if (cost_diff > k || i + j + 1 - m > n) continue; // Case 1 dp[i][j][k][m] += dp[i - 1][j - 1][k - cost_diff][m]; // Case 2 if (m) dp[i][j][k][m] += (3 - m) * dp[i - 1][j - 1][k - cost_diff][m - 1]; // Case 3 dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - cost_diff][m]; // Case 4 if (m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - cost_diff][m - 1]; if (m == 2) { if (i == n) dp[i][j][k][m] += dp[i - 1][j][k - cost_diff][m - 1]; else if (j > 1) dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - cost_diff][m - 1]; } // Case 5 if (m == 2) { if (i == n) dp[i][j][k][m] += dp[i - 1][j + 1][k - cost_diff][m]; else dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - cost_diff][m]; } else if (m == 1) dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - cost_diff][m]; else dp[i][j][k][m] += j * (j + 1) * dp[i - 1][j + 1][k - cost_diff][m]; dp[i][j][k][m] %= MOD; } } } } long long ans = 0; for (int i = 0; i <= l; i++) ans += dp[n][1][i][2]; cout << ans % MOD; } } void Solve(int Test) { cin >> n >> l; for(int i = 0; i < n; ++ i) cin >> a[i]; if(n <= 8) { Sub1(); return; } if(n <= 14 && l <= 100) { Sub2::solve(); } else { Full::solve(); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); if(fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } int test = 1; // cin >> test; for(int i = 1; i <= test; ++ i) { Solve(i); } } /*no pain no gain*/

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:131:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     freopen(Task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:132:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |     freopen(Task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...