| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 631363 | 2022-08-18T03:46:33 Z | uylulu | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 395 ms | 159904 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
const int N = 1e7,len = 1e5;
int mx[N + 1],dp[N + 1],num[len + 1];
int m,q,lim;
int lcm(int a,int b) {
return a*b/(__gcd(a,b));
}
void init() {
lim = num[1];
for(int i = 2;i <= m;i++) {
if(lim > N) break;
lim = lcm(lim,num[i]);
}
for(int i = 1;i <= m;i++) {
for(int j = 1;num[i]*j <= N;j++) {
mx[num[i]*j] = max(num[i],mx[num[i]*j]);
}
}
dp[0] = 0;
for(int i = 1;i < num[m];i++) {
dp[i] = 1;
}
int lst = 0,temp = 0;
for(int i = 1;i < num[m];i++) {
if(temp < (mx[i] - 1) - (num[m] - i)) {
temp = (mx[i] - 1) - (num[m] - i);
lst = i;
}
}
for(int i = num[m];i < lim;i++) {
while(mx[lst] - 1 < (i - lst)) lst++;
dp[i] = dp[lst] + 1;
}
}
signed main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin>>m>>q;
for(int i = 1;i <= m;i++) cin>>num[i];
init();
while(q--) {
int x;
cin>>x;
if(x >= lim) {
cout<<"oo"<<endl;
} else {
cout<<dp[x]<<endl;
}
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 30 ms | 39404 KB | Output is correct |
| 2 | Runtime error | 154 ms | 159100 KB | Execution killed with signal 11 |
| 3 | Correct | 41 ms | 40460 KB | Output is correct |
| 4 | Runtime error | 132 ms | 159064 KB | Execution killed with signal 11 |
| 5 | Correct | 74 ms | 78484 KB | Output is correct |
| 6 | Correct | 32 ms | 39396 KB | Output is correct |
| 7 | Correct | 45 ms | 40448 KB | Output is correct |
| 8 | Correct | 52 ms | 42900 KB | Output is correct |
| 9 | Runtime error | 167 ms | 158992 KB | Execution killed with signal 11 |
| 10 | Runtime error | 191 ms | 159148 KB | Execution killed with signal 11 |
| 11 | Correct | 132 ms | 78464 KB | Output is correct |
| 12 | Runtime error | 137 ms | 159112 KB | Execution killed with signal 11 |
| 13 | Runtime error | 254 ms | 159028 KB | Execution killed with signal 11 |
| 14 | Runtime error | 304 ms | 159184 KB | Execution killed with signal 11 |
| 15 | Correct | 86 ms | 78468 KB | Output is correct |
| 16 | Runtime error | 165 ms | 159048 KB | Execution killed with signal 11 |
| 17 | Runtime error | 172 ms | 159096 KB | Execution killed with signal 11 |
| 18 | Runtime error | 128 ms | 159048 KB | Execution killed with signal 11 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 157 ms | 159200 KB | Execution killed with signal 11 |
| 2 | Correct | 107 ms | 78912 KB | Output is correct |
| 3 | Runtime error | 291 ms | 159660 KB | Execution killed with signal 11 |
| 4 | Runtime error | 158 ms | 159084 KB | Execution killed with signal 11 |
| 5 | Runtime error | 269 ms | 159436 KB | Execution killed with signal 11 |
| 6 | Correct | 83 ms | 78452 KB | Output is correct |
| 7 | Runtime error | 140 ms | 159196 KB | Execution killed with signal 11 |
| 8 | Runtime error | 156 ms | 159088 KB | Execution killed with signal 11 |
| 9 | Runtime error | 284 ms | 159584 KB | Execution killed with signal 11 |
| 10 | Runtime error | 306 ms | 159636 KB | Execution killed with signal 11 |
| 11 | Runtime error | 291 ms | 159636 KB | Execution killed with signal 11 |
| 12 | Runtime error | 185 ms | 159012 KB | Execution killed with signal 11 |
| 13 | Runtime error | 136 ms | 159144 KB | Execution killed with signal 11 |
| 14 | Runtime error | 154 ms | 159044 KB | Execution killed with signal 11 |
| 15 | Runtime error | 248 ms | 159396 KB | Execution killed with signal 11 |
| 16 | Correct | 102 ms | 78808 KB | Output is correct |
| 17 | Runtime error | 248 ms | 159032 KB | Execution killed with signal 11 |
| 18 | Correct | 189 ms | 78900 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 263 ms | 159440 KB | Execution killed with signal 11 |
| 2 | Runtime error | 294 ms | 159440 KB | Execution killed with signal 11 |
| 3 | Runtime error | 344 ms | 159448 KB | Execution killed with signal 11 |
| 4 | Correct | 328 ms | 78808 KB | Output is correct |
| 5 | Runtime error | 185 ms | 159852 KB | Execution killed with signal 11 |
| 6 | Runtime error | 295 ms | 159092 KB | Execution killed with signal 11 |
| 7 | Runtime error | 293 ms | 159828 KB | Execution killed with signal 11 |
| 8 | Runtime error | 302 ms | 159468 KB | Execution killed with signal 11 |
| 9 | Runtime error | 328 ms | 159428 KB | Execution killed with signal 11 |
| 10 | Correct | 172 ms | 78496 KB | Output is correct |
| 11 | Runtime error | 219 ms | 159080 KB | Execution killed with signal 11 |
| 12 | Runtime error | 290 ms | 159052 KB | Execution killed with signal 11 |
| 13 | Runtime error | 300 ms | 159228 KB | Execution killed with signal 11 |
| 14 | Runtime error | 217 ms | 159104 KB | Execution killed with signal 11 |
| 15 | Runtime error | 264 ms | 159136 KB | Execution killed with signal 11 |
| 16 | Runtime error | 303 ms | 159084 KB | Execution killed with signal 11 |
| 17 | Runtime error | 335 ms | 159408 KB | Execution killed with signal 11 |
| 18 | Runtime error | 342 ms | 159444 KB | Execution killed with signal 11 |
| 19 | Runtime error | 165 ms | 159056 KB | Execution killed with signal 11 |
| 20 | Runtime error | 341 ms | 159492 KB | Execution killed with signal 11 |
| 21 | Runtime error | 226 ms | 159092 KB | Execution killed with signal 11 |
| 22 | Runtime error | 356 ms | 159880 KB | Execution killed with signal 11 |
| 23 | Runtime error | 214 ms | 159344 KB | Execution killed with signal 11 |
| 24 | Correct | 279 ms | 78820 KB | Output is correct |
| 25 | Runtime error | 279 ms | 159120 KB | Execution killed with signal 11 |
| 26 | Correct | 374 ms | 78784 KB | Output is correct |
| 27 | Runtime error | 363 ms | 159868 KB | Execution killed with signal 11 |
| 28 | Correct | 228 ms | 78900 KB | Output is correct |
| 29 | Runtime error | 291 ms | 159852 KB | Execution killed with signal 11 |
| 30 | Runtime error | 290 ms | 159612 KB | Execution killed with signal 11 |
| 31 | Runtime error | 153 ms | 159060 KB | Execution killed with signal 11 |
| 32 | Correct | 243 ms | 78884 KB | Output is correct |
| 33 | Runtime error | 135 ms | 159052 KB | Execution killed with signal 11 |
| 34 | Runtime error | 300 ms | 159904 KB | Execution killed with signal 11 |
| 35 | Runtime error | 144 ms | 159124 KB | Execution killed with signal 11 |
| 36 | Correct | 395 ms | 79180 KB | Output is correct |
| 37 | Runtime error | 203 ms | 159844 KB | Execution killed with signal 11 |
| 38 | Runtime error | 246 ms | 159124 KB | Execution killed with signal 11 |
| 39 | Runtime error | 145 ms | 159052 KB | Execution killed with signal 11 |
| 40 | Runtime error | 230 ms | 159156 KB | Execution killed with signal 11 |
| 41 | Correct | 228 ms | 78956 KB | Output is correct |
| 42 | Runtime error | 273 ms | 159116 KB | Execution killed with signal 11 |