Submission #46878

#TimeUsernameProblemLanguageResultExecution timeMemory
46878qoo2p5Skyscraper (JOI16_skyscraper)C++17
100 / 100
389 ms130784 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int INF = (int) 1e9 + 1e6; const ll LINF = (ll) 1e18 + 1e9; const ll MOD = (ll) 1e9 + 7; #define sz(x) (int) (x).size() #define mp(x, y) make_pair(x, y) #define pb push_back #define all(x) (x).begin(), (x).end() #define lb(s, t, x) (int) (lower_bound(s, t, x) - s) #define ub(s, t, x) (int) (upper_bound(s, t, x) - s) #define rep(i, f, t) for (auto i = f; i < t; ++(i)) #define per(i, f, t) for (auto i = (f); i >= (t); --(i)) ll power(ll x, ll y, ll mod = MOD) { if (y == 0) { return 1; } if (y & 1) { return power(x, y - 1, mod) * x % mod; } else { ll tmp = power(x, y / 2, mod); return tmp * tmp % mod; } } template<typename A, typename B> bool mini(A &x, const B &y) { if (y < x) { x = y; return true; } return false; } template<typename A, typename B> bool maxi(A &x, const B &y) { if (x < y) { x = y; return true; } return false; } void add(ll &x, ll y) { x += y; if (x >= MOD) x -= MOD; if (x < 0) x += MOD; } void run(); #define TASK "" int main() { #ifdef LOCAL if (strlen(TASK) > 0) { cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl; } #endif #ifndef LOCAL if (strlen(TASK)) { freopen(TASK ".in", "r", stdin); freopen(TASK ".out", "w", stdout); } ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cout << fixed << setprecision(12); run(); return 0; } // == SOLUTION == // const int N = 105; const int L = 1005; int n, l; int a[N]; ll dp[N][N][L][3]; void run() { cin >> n >> l; if (n == 1) { cout << "1\n"; return; } rep(i, 0, n) { cin >> a[i]; } sort(a, a + n); dp[0][0][0][0] = 1; rep(i, 0, n) { int w = (i == 0 ? a[i] : a[i] - a[i - 1]); rep(j, 0, n) { rep(t, 0, l) { rep(k, 0, 3) { int places = j + 1 - k; int to_add = 2 * j - k; int cost = t + to_add * w; ll cur = dp[i][j][t][k]; if (cost <= l) { add(dp[i + 1][j + 1][cost][k], (cur * places) % MOD); if (j > 0) { add(dp[i + 1][j][cost][k], (cur * to_add) % MOD); } if (j >= 2) { add(dp[i + 1][j - 1][cost][k], (cur * (j - 1)) % MOD); } if (k == 0) { add(dp[i + 1][j + 1][cost][1], (cur * 2) % MOD); if (j > 0) { add(dp[i + 1][j][cost][1], (cur * 2) % MOD); } } else if (k == 1) { add(dp[i + 1][j + 1][cost][2], cur); if (j > 0) { add(dp[i + 1][j][cost][2], cur); } } } } } } } ll ans = 0; rep(i, 0, l + 1) { add(ans, dp[n][1][i][2]); } cout << ans << "\n"; }

Compilation message (stderr)

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