結果

問題 No.1956 猫の額
ユーザー suisen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0