Submission #138405

#TimeUsernameProblemLanguageResultExecution timeMemory
138405silxikysBrunhilda’s Birthday (BOI13_brunhilda)C++14
21.43 / 100
52 ms36724 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = 1e5+5, INF = 2e9+9; int m, Q; int dp[10000005]; vector<int> primes; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> m >> Q; for (int i = 0; i < m; i++) { int p; cin >> p; primes.push_back(p); } sort(primes.begin(),primes.end()); int maxPrime = primes.back(); for (int i = 1; i < maxPrime; i++) { dp[i] = 1; } for (int i = maxPrime; i <= 10000; i++) { dp[i] = INF; for (int j: primes) { //cout << i << ' ' << j << ": " << (i-(i%j)) << '\n'; dp[i] = min(dp[i],1+dp[i-(i%j)]); } } /* for (int i = 1; i <= 10; i++) { cout << i << ": " << dp[i] << '\n'; } */ while (Q--) { int qi; cin >> qi; if (dp[qi] == INF) cout << "oo\n"; else cout << dp[qi] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...