結果
問題 | No.288 貯金箱の仕事 |
ユーザー |
![]() |
提出日時 | 2021-05-13 11:21:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 876 bytes |
コンパイル時間 | 3,472 ms |
コンパイル使用メモリ | 194,916 KB |
最終ジャッジ日時 | 2025-01-21 10:32:35 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
//https://ncode.syosetu.com/n4830bu/288/ #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll N, M; cin >> N >> M; vector<ll> A(N), K(N); for (auto&& a : A) { cin >> a; } for (auto&& k : K) { cin >> k; } M *= -1; for (int i = 0; i < N; i++) { M += A[i] * K[i]; } ll maine = 3e18; if (M >= 0) { vector<ll> dp(300000, (ll)3e18); dp[0] = 0; for (int i = 0; i < N; i++) { for (int x = 0; x <= 290000; x++) { dp[x + A[i]] = min(dp[x + A[i]], dp[x] + 1ll); } } for (int i = M % A.back(); i < 290000; i += A.back()) { if (i > M) break; maine = min(maine, dp[i] + (M - i) / A.back()); } } cout << (maine > (ll)(2e18) ? -1 : maine) << endl; }