Submission #1265301

#TimeUsernameProblemLanguageResultExecution timeMemory
1265301shibaiSkyscraper (JOI16_skyscraper)C++20
5 / 100
1 ms584 KiB
#include <bits/stdc++.h> using namespace std; using namespace chrono; #define io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fi first #define se second #define eb emplace_back #define endl '\n' //#define int long long typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpii; const int INF = 1e9; const int MOD = 998244353; const ll LINF = 1e18; #define TIMER_START auto start_time = high_resolution_clock::now(); #define TIMER_END auto end_time = high_resolution_clock::now(); \ auto duration = duration_cast<milliseconds>(end_time - start_time).count(); \ cerr << "\nExecution Time: " << duration << " ms\n"; void fname(const string& task_name) { freopen((task_name + ".inp").c_str(), "r", stdin); freopen((task_name + ".out").c_str(), "w", stdout); } void sadd (int &x, int y) { x += y; if(x >= MOD) x -= MOD; } void ssub (int &x, int y) { x -= y; if(x < 0) x += MOD; } void smul (int &x, int y) { y = max(y, 0); x = 1LL * x * y % MOD; } int add (int x, int y) { x += y; if(x >= MOD) x -= MOD; return x; } int sub (int x, int y) { x -= y; if(x < 0) x += MOD; return x; } int mul (int x, int y) { y = max(y, 0); x = 1LL * x * y % MOD; return x; } int n, L, a[105], dp[105][105][1005][3]; void solve() { cin >> n >> L; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); if(n == 1) { cout << 1; exit(0); } if(n == 2) { cout << 2; exit(0); } 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 < 3; m++) { int cost = (2 * j - m) * (a[i + 1] - a[i]); if(cost > k || i + j + 1 - m > n) continue; if(m) dp[i][j][k][m] = mul(3 - m, dp[i - 1][j - 1][k - cost][m - 1]); sadd(dp[i][j][k][m], dp[i - 1][j - 1][k - cost][m]); sadd(dp[i][j][k][m], mul(2 * j - m, dp[i - 1][j][k - cost][m])); if(m == 1) { sadd(dp[i][j][k][m], mul(2 * j, dp[i - 1][j][k - cost][0])); } if(m == 2) { if(i == n) { sadd(dp[i][j][k][m], dp[i - 1][j][k - cost][m - 1]); } else if(j > 1) { sadd(dp[i][j][k][m], mul(j - 1, dp[i - 1][j][k - cost][m - 1])); } } if(m == 2) { if(i == n) { sadd(dp[i][j][k][m], dp[i - 1][j + 1][k - cost][m]); } else { sadd(dp[i][j][k][m], mul(mul(j, j - 1), dp[i - 1][j + 1][k - cost][m])); } } else { sadd(dp[i][j][k][m], mul(mul(j, j + 1 - m), dp[i - 1][j + 1][k - cost][m])); } } } } } int ans = 0; for (int i = 0; i <= L; i++) { sadd(ans, dp[n][1][i][2]); } cout << ans; } int32_t main() { io; // fname("task"); TIMER_START; solve(); TIMER_END; return 0; }

Compilation message (stderr)

skyscraper.cpp: In function 'void fname(const string&)':
skyscraper.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen((task_name + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen((task_name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...