結果
問題 | No.1956 猫の額 |
ユーザー |
|
提出日時 | 2022-05-24 00:55:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 897 bytes |
コンパイル時間 | 931 ms |
コンパイル使用メモリ | 85,088 KB |
最終ジャッジ日時 | 2025-01-29 14:55:48 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 12 MLE * 9 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>#include <atcoder/modint>using mint = atcoder::modint;int main() {int n, m, c;std::cin >> n >> m >> c;mint::set_mod(m);std::vector<int> a(n);for (auto &e : a) std::cin >> e;std::sort(a.begin(), a.end(), std::greater<int>());const int s = std::accumulate(a.begin(), a.end(), 0);bool take_compl = 2 * c >= n;if (take_compl) {c = n - c;}std::vector dp(c + 1, std::vector<mint>(s + 1));dp[0][0] = 1;for (int val : a) {for (int num = s / val; num >= 1; --num) {for (int sum = num * val; sum <= s; ++sum) {dp[num][sum] += dp[num - 1][sum - val];}}}for (int sum = 1; sum <= s; ++sum) {std::cout << dp[c][take_compl ? s - sum : sum].val() << " \n"[sum == s];}return 0;}