結果
問題 | No.288 貯金箱の仕事 |
ユーザー |
|
提出日時 | 2016-07-19 18:24:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,632 ms / 2,000 ms |
コード長 | 1,247 bytes |
コンパイル時間 | 409 ms |
コンパイル使用メモリ | 54,964 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 17:23:56 |
合計ジャッジ時間 | 26,534 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include <cstdio> #include <vector> #include <algorithm> #include <numeric> #include <array> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x) typedef long long ll; using namespace std; template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; } const int W = 500; const ll infty = ll(1e18)+9; int main() { int n; ll m; scanf("%d%lld", &n, &m); vector<int> a(n); repeat (i,n) scanf("%d", &a[i]); vector<ll> k(n); repeat (i,n) scanf("%lld", &k[i]); ll x = whole(inner_product, a, k.begin(), 0ll) - m; ll ans = infty; if (x >= 0) { int l = min<ll>(3e5, x+1); // magic array<ll,W+2> dp = {}; whole(fill, dp, infty); dp[0] = 0; repeat (acc,l) { int i = acc % dp.size(); if (dp[i] == infty) continue; repeat (j,n) { setmin(dp[(i + a[j]) % dp.size()], dp[i] + 1); if ((x - acc) % a[j] == 0) { setmin(ans, dp[i] + (x - acc) / a[j]); } } dp[i] = infty; } } if (ans == infty) ans = -1; printf("%lld\n", ans); return 0; }