Submission #1069192

#TimeUsernameProblemLanguageResultExecution timeMemory
1069192ortsacBrunhilda’s Birthday (BOI13_brunhilda)C++17
100 / 100
193 ms158032 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<long long, long long> #define fr first #define se second int inf = 0x3f3f3f3f3f3f3f3f; const int MAXN = 1e7 + 10; int dp[MAXN + 10], trans[MAXN + 10]; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, q; cin >> n >> q; for (int i = 0; i < n; i++) { int a; cin >> a; for (int j = (a - 1); j <= MAXN; j += a) { trans[j] = a - 1; } trans[MAXN] = max(trans[MAXN], MAXN % a); } for (int i = MAXN; i >= 1; i--) { trans[i] = max(trans[i], trans[i + 1] - 1); } for (int i = 1; i <= MAXN; i++) { dp[i] = inf; dp[i] = min(dp[i], dp[i - trans[i]] + 1); } while (q--) { int x; cin >> x; if (dp[x] == inf) cout << "oo\n"; else cout << dp[x] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...