Submission #307086

#TimeUsernameProblemLanguageResultExecution timeMemory
307086RainbowbunnyBrunhilda’s Birthday (BOI13_brunhilda)C++17
100 / 100
823 ms236924 KiB
#include <bits/stdc++.h> #define int long long #define mp make_pair #define eb emplace_back #define fi first #define se second using namespace std; using cd = complex <double>; const long long INF = 1e15; const int mod = 998244353;//1e9 + 7;//786433; const double Pi = acos(-1); void Fastio() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int m, q, p; int Seive[20000005], dp[10000005]; signed main() { Fastio(); cin >> m >> q; for(int i = 1; i <= m; i++) { cin >> p; for(int j = p - 1; j <= 20000000; j = j + p) { Seive[j] = max(Seive[j], p - 1); } } for(int i = 20000000; i > 1; i--) { Seive[i - 1] = max(Seive[i - 1], Seive[i] - 1); } for(int i = 1; i <= 10000000; i++) { dp[i] = 999999999; dp[i] = dp[i - Seive[i]] + 1; } while(q--) { int n; cin >> n; if(dp[n] >= 10000005) { cout << "oo\n"; continue; } cout << dp[n] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...