Submission #31867

#TimeUsernameProblemLanguageResultExecution timeMemory
31867huynd2001Brunhilda’s Birthday (BOI13_brunhilda)C++14
8.89 / 100
453 ms80532 KiB
/*huypheu 2 2 2 3 5 6 */ #include <bits/stdc++.h> #define oo (INT_MAX/2) using namespace std; int pri[10000005],dp[10000005]; int a[100005]; int main() { int n,q; cin >> n >> q; for(int i=1;i<=n;i++) { cin >> a[i]; } int maxo=10000007; for(int i=1;i<=maxo;i++) dp[i]=oo; for(int i=1;i<=n;i++) { for(int j=0;j<=(maxo/a[i]);j++) { pri[a[i]*j]=a[i]; } } dp[0]=0; int curl=0,curr=0+pri[0]-1; for(int i=1;i<=maxo;i++) { while(i>curr) { curl++; curr=curl+pri[curl]-1; } if(curl==i) break; dp[i]=min(dp[curl]+1,dp[i]); } // for(int i=1;i<=10;i++) // { // cout << dp[i] << " "; // } // cout << endl; for(int i=1;i<=q;i++) { int b; cin >> b; if(dp[b]>=maxo) cout << "oo\n"; else cout << dp[b] << "\n"; } return 0; }

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:23:35: warning: iteration 10000004u invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i=1;i<=maxo;i++) dp[i]=oo;
                                   ^
brunhilda.cpp:23:15: note: containing loop
  for(int i=1;i<=maxo;i++) dp[i]=oo;
               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...