結果
| 問題 | No.137 貯金箱の焦り |
| コンテスト | |
| ユーザー |
 a_s_k
|
| 提出日時 | 2026-05-15 03:59:07 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 213 ms / 5,000 ms |
| コード長 | 3,969 bytes |
| 記録 | |
| コンパイル時間 | 7,307 ms |
| コンパイル使用メモリ | 388,056 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-05-15 03:59:19 |
| 合計ジャッジ時間 | 10,953 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/vector:67,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/functional:66,
from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:55,
from main.cpp:1:
In function '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = atcoder::dynamic_modint<-1>*; _ForwardIterator = atcoder::dynamic_modint<-1>*]',
inlined from 'constexpr _ForwardIterator std::__uninitialized_copy_a(_InputIterator, _Sentinel, _ForwardIterator, allocator<_Tp>&) [with _InputIterator = atcoder::dynamic_modint<-1>*; _Sentinel = atcoder::dynamic_modint<-1>*; _ForwardIterator = atcoder::dynamic_modint<-1>*; _Tp = atcoder::dynamic_modint<-1>]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_uninitialized.h:635:32,
inlined from 'constexpr std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = atcoder::dynamic_modint<-1>; _Alloc = std::allocator<atcoder::dynamic_modint<-1> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/vector.tcc:257:35,
inlined from 'int main()' at main.cpp:161:14:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_uninitialized.h:273:31: warning: 'void* __builtin_memcpy(void*, const void*, long unsigned int)' writing between 1 and 200004 bytes into a region of size 0 overflows the destination [-Wstringop-overflow=]
273 | __builtin_memcpy(std::__niter_base(__result),
| ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
274 | std::__niter_base(__first),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~
275 | __n * sizeof(_ValT));
| ~~~~~~~~~~~~~~~~~~~~
In
ソースコード
#include "bits/stdc++.h"
#include "atcoder/all"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define rep(i, m, n) for (ll i = (ll)m; i < (ll)n; i++)
#define drep(i, m, n) for (ll i = m - 1; i >= n; i--)
#define Endl endl
#define all(a) a.begin(), a.end()
#define pr(i, j) make_pair(i, j)
#define isin(x, l, r) (l <= x && x < r)
template <typename T>
bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
};
template <typename T>
bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
};
#define srt(ar) sort(ar.begin(), ar.end())
#define rev(ar) reverse(ar.begin(), ar.end())
#define jge(f, s, t) cout << (f ? s : t) << endl
template <typename T>
using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define printar(ar) \
do \
{ \
for (auto dbg : ar) \
{ \
cout << dbg << " "; \
} \
cout << endl; \
} while (0)
const ll inf = 1e18;
const ld pi = 3.14159265358979;
const ld eps = 1e-9;
template <class T, ll n, ll idx = 0>
auto make_vec(const ll (&d)[n], const T &init) noexcept
{
if constexpr (idx < n)
return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));
else
return init;
}
template <class T, ll n>
auto make_vec(const ll (&d)[n]) noexcept
{
return make_vec(d, T{});
}
//////////////// 以下を貼る ////////////////
template <class T>
size_t HashCombine(const size_t seed, const T &v)
{
return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}
/* pair用 */
template <class T, class S>
struct std::hash<std::pair<T, S>>
{
size_t operator()(const std::pair<T, S> &keyval) const noexcept
{
return HashCombine(std::hash<T>()(keyval.first), keyval.second);
}
};
/* vector用 */
template <class T>
struct std::hash<std::vector<T>>
{
size_t operator()(const std::vector<T> &keyval) const noexcept
{
size_t s = 0;
for (auto &&v : keyval)
s = HashCombine(s, v);
return s;
}
};
/* tuple用 */
template <int N>
struct HashTupleCore
{
template <class Tuple>
size_t operator()(const Tuple &keyval) const noexcept
{
size_t s = HashTupleCore<N - 1>()(keyval);
return HashCombine(s, std::get<N - 1>(keyval));
}
};
template <>
struct HashTupleCore<0>
{
template <class Tuple>
size_t operator()(const Tuple &keyval) const noexcept { return 0; }
};
template <class... Args>
struct std::hash<std::tuple<Args...>>
{
size_t operator()(const tuple<Args...> &keyval) const noexcept
{
return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);
}
};
////////////////////////////////////////////
using mint = modint;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m;
cin >> n >> m;
modint::set_mod(1234567891);
vector<ll> a(n);
rep(i, 0, n)
{
cin >> a[i];
}
vector<mint> dp(50001);
dp[0] = 1;
rep(i, 0, 62)
{
rep(j, 0, n)
{
drep(k, 50001, 0)
{
if (k - a[j] >= 0)
{
dp[k] += dp[k - a[j]];
}
}
}
vector<mint> cp(50001);
rep(j, 0, 50001)
{
if (m % 2 == j % 2)
{
cp[j / 2] += dp[j];
}
}
dp = cp;
m /= 2;
}
cout << dp[0].val() << endl;
}