Submission #559574

#TimeUsernameProblemLanguageResultExecution timeMemory
559574TrunktyBrunhilda’s Birthday (BOI13_brunhilda)C++14
100 / 100
315 ms119376 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; #define DEBUG #ifdef DEBUG #define debug(x) cout << #x << ": " << x << endl #else #define debug(x) #endif int m,q,mini=2e9; int maxi[10000005]; int low[10000005]; int dp[10000005]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> m >> q; for(int i=1;i<=m;i++){ int a; cin >> a; for(int j=a;j<=1e7;j+=a){ maxi[j] = max(maxi[j],a); } mini = min(mini,10000000-10000000%a); } for(int i=1e7;i>=1;i--){ low[i] = mini; mini = min(mini,i-maxi[i]); } for(int i=1;i<=1e7;i++){ dp[i] = 2e9; dp[i] = dp[low[i]]+1; } for(int i=1;i<=q;i++){ int a; cin >> a; if(dp[a]<2e9){ cout << dp[a] << "\n"; } else{ cout << "oo" << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...