제출 #589387

#제출 시각아이디문제언어결과실행 시간메모리
589387Loki_NguyenSkyscraper (JOI16_skyscraper)C++14
100 / 100
1097 ms24376 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<int, pii> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 102; const int M = 10002; const int mod = 1e9 + 7; const int base = 75; const ll inf = 1e12; int n, t, tong; int k, m, a[N], b[N], dp[2][N][M][3]; int ans; void add(int& x, int y) { x += y; if (x >= mod) x -= mod; } void sol() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i], b[i] = i; if (n == 1) { cout << 1 << '\n'; return; } sort(a + 1, a + 1 + n); reverse(a + 1, a + 1 + n); dp[1][1][a[1] * 2][0] = 1; dp[1][1][a[1]][1] = 2; for (int i = 1; i < n; i++) { memset(dp[(i&1)^1], 0, sizeof(dp[(i&1)^1])); for (int j = 1; j <= i; j++) { for (int p = 0; p < M; p++) { for (int q = 0; q < 3; q++) { if (dp[i&1][j][p][q] == 0) continue; if (p + a[i + 1] * 2 < M) add(dp[(i&1)^1][j + 1][p + a[i + 1] * 2][q], 1ll * dp[i&1][j][p][q] * (j + 1 - q) % mod); if (q < 2 && p + a[i + 1] < M) add(dp[(i&1)^1][j + 1][p + a[i + 1]][q + 1], 1ll * dp[i&1][j][p][q] * (2 - q) % mod); add(dp[(i&1)^1][j][p][q], 1ll * dp[i&1][j][p][q] * (2 * j - q) % mod); if (q < 2 && p >= a[i + 1]) add(dp[(i&1)^1][j][p - a[i + 1]][q + 1], 1ll * dp[i&1][j][p][q] * (2 - q) % mod); if (j > 1 && p >= a[i + 1] * 2) add(dp[(i&1)^1][j - 1][p - a[i + 1] * 2][q], 1ll * dp[i&1][j][p][q] * (j - 1) % mod); } } } } for (int i = 0; i <= k; i++) add(ans, dp[n&1][1][i][2]); cout << ans << '\n'; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "tests" if (fopen(task ".inp", "r")) { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } int test = 1; // cin >> test; while (test-- > 0) sol(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

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