結果
問題 | No.1956 猫の額 |
ユーザー | 👑 hos.lyric |
提出日時 | 2022-05-24 01:57:07 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 132 ms / 10,000 ms |
コード長 | 3,131 bytes |
コンパイル時間 | 2,748 ms |
コンパイル使用メモリ | 160,952 KB |
実行使用メモリ | 13,328 KB |
最終ジャッジ日時 | 2023-10-20 18:41:33 |
合計ジャッジ時間 | 5,586 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 129 ms
13,328 KB |
testcase_01 | AC | 17 ms
13,328 KB |
testcase_02 | AC | 131 ms
13,328 KB |
testcase_03 | AC | 19 ms
13,328 KB |
testcase_04 | AC | 132 ms
13,328 KB |
testcase_05 | AC | 116 ms
13,328 KB |
testcase_06 | AC | 129 ms
13,328 KB |
testcase_07 | AC | 61 ms
13,328 KB |
testcase_08 | AC | 105 ms
13,256 KB |
testcase_09 | AC | 24 ms
13,288 KB |
testcase_10 | AC | 93 ms
13,216 KB |
testcase_11 | AC | 50 ms
13,128 KB |
testcase_12 | AC | 80 ms
13,176 KB |
testcase_13 | AC | 8 ms
13,028 KB |
testcase_14 | AC | 24 ms
12,992 KB |
testcase_15 | AC | 18 ms
13,320 KB |
testcase_16 | AC | 120 ms
13,296 KB |
testcase_17 | AC | 132 ms
13,328 KB |
testcase_18 | AC | 130 ms
13,328 KB |
testcase_19 | AC | 131 ms
13,328 KB |
testcase_20 | AC | 131 ms
13,328 KB |
ソースコード
#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx") #include <cassert> #include <cmath> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; using Int = long long; template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } unsigned M; void Add(unsigned &t, unsigned f) { t += f; t = (t >= M) ? (t - M) : t; } void Sub(unsigned &t, unsigned f) { t -= f; t = (t >= M) ? (t + M) : t; } int N, K; int A[110]; int L; int S, T; unsigned dp[47][50'010]; unsigned ans0[50'010]; unsigned ans1[50'010]; int main() { for (; ~scanf("%d%u%d", &N, &M, &K); ) { for (int i = 0; i < N; ++i) { scanf("%d", &A[i]); } sort(A, A + N); L = ((N + 1) + 1) / 2; assert(N < 2 * L); S = 0; for (int i = 0; i < N; ++i) { S += A[i]; } T = S / 2; M *= 2; // + #ifdef LOCAL memset(dp, 0, sizeof(dp)); #endif dp[0][0] = 1 % M; for (int i = 0; i < N; ++i) { for (int k = L; --k >= 0; ) if (i >= k) { for (int x = 0; x + A[i] <= T; ++x) { Add(dp[k + 1][x + A[i]], dp[k][x]); } } if (i + 1 >= L) { for (int x = 0; x <= T; ++x) { Add(dp[0][x], dp[L][x]); } memset(dp[L], 0, (T + 1) * sizeof(dp[0][0])); } } memcpy(ans0, dp[K % L], (T + 1) * sizeof(dp[0][0])); memcpy(ans1, dp[(N - K) % L], (T + 1) * sizeof(dp[0][0])); // - memset(dp, 0, sizeof(dp)); dp[0][0] = 1 % M; for (int i = 0; i < N; ++i) { for (int k = L; --k >= 0; ) if (i >= k) { for (int x = 0; x + A[i] <= T; ++x) { Add(dp[k + 1][x + A[i]], dp[k][x]); } } if (i + 1 >= L) { for (int x = 0; x <= T; ++x) { Sub(dp[0][x], dp[L][x]); } memset(dp[L], 0, (T + 1) * sizeof(dp[0][0])); } } for (int x = 0; x <= T; ++x) { unsigned a = ans0[x]; (K >= L) ? Sub(a, dp[K - L][x]) : Add(a, dp[K][x]); assert(a % 2 == 0); ans0[x] = a / 2; } for (int x = 0; x <= T; ++x) { unsigned a = ans1[x]; (N - K >= L) ? Sub(a, dp[(N - K) - L][x]) : Add(a, dp[N - K][x]); assert(a % 2 == 0); ans1[x] = a / 2; } for (int x = 1; x <= S; ++x) { if (x > 1) printf(" "); printf("%u", (x <= T) ? ans0[x] : ans1[S - x]); } puts(""); } return 0; }