| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 631358 | 2022-08-18T03:42:01 Z | uylulu | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 438 ms | 160012 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[N + 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] = num[i];
}
}
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 | 25 ms | 39436 KB | Output is correct |
| 2 | Runtime error | 147 ms | 159060 KB | Execution killed with signal 11 |
| 3 | Correct | 30 ms | 40456 KB | Output is correct |
| 4 | Runtime error | 139 ms | 159072 KB | Execution killed with signal 11 |
| 5 | Correct | 83 ms | 78540 KB | Output is correct |
| 6 | Correct | 25 ms | 39452 KB | Output is correct |
| 7 | Correct | 33 ms | 40460 KB | Output is correct |
| 8 | Correct | 35 ms | 42956 KB | Output is correct |
| 9 | Runtime error | 185 ms | 159112 KB | Execution killed with signal 11 |
| 10 | Runtime error | 195 ms | 159180 KB | Execution killed with signal 11 |
| 11 | Correct | 94 ms | 78476 KB | Output is correct |
| 12 | Runtime error | 128 ms | 159104 KB | Execution killed with signal 11 |
| 13 | Runtime error | 246 ms | 159108 KB | Execution killed with signal 11 |
| 14 | Runtime error | 221 ms | 159100 KB | Execution killed with signal 11 |
| 15 | Correct | 74 ms | 78460 KB | Output is correct |
| 16 | Runtime error | 159 ms | 159216 KB | Execution killed with signal 11 |
| 17 | Runtime error | 150 ms | 159048 KB | Execution killed with signal 11 |
| 18 | Runtime error | 128 ms | 159080 KB | Execution killed with signal 11 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 168 ms | 159188 KB | Execution killed with signal 11 |
| 2 | Correct | 86 ms | 78880 KB | Output is correct |
| 3 | Runtime error | 297 ms | 159620 KB | Execution killed with signal 11 |
| 4 | Runtime error | 153 ms | 159112 KB | Execution killed with signal 11 |
| 5 | Runtime error | 208 ms | 159436 KB | Execution killed with signal 11 |
| 6 | Correct | 76 ms | 78540 KB | Output is correct |
| 7 | Runtime error | 155 ms | 159252 KB | Execution killed with signal 11 |
| 8 | Runtime error | 157 ms | 159120 KB | Execution killed with signal 11 |
| 9 | Runtime error | 252 ms | 159616 KB | Execution killed with signal 11 |
| 10 | Runtime error | 266 ms | 159604 KB | Execution killed with signal 11 |
| 11 | Runtime error | 257 ms | 159392 KB | Execution killed with signal 11 |
| 12 | Runtime error | 193 ms | 159060 KB | Execution killed with signal 11 |
| 13 | Runtime error | 151 ms | 159064 KB | Execution killed with signal 11 |
| 14 | Runtime error | 160 ms | 159128 KB | Execution killed with signal 11 |
| 15 | Runtime error | 241 ms | 159348 KB | Execution killed with signal 11 |
| 16 | Correct | 91 ms | 78900 KB | Output is correct |
| 17 | Runtime error | 225 ms | 159128 KB | Execution killed with signal 11 |
| 18 | Correct | 174 ms | 78952 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 228 ms | 159528 KB | Execution killed with signal 11 |
| 2 | Runtime error | 262 ms | 159444 KB | Execution killed with signal 11 |
| 3 | Runtime error | 264 ms | 159484 KB | Execution killed with signal 11 |
| 4 | Correct | 260 ms | 78832 KB | Output is correct |
| 5 | Runtime error | 177 ms | 159916 KB | Execution killed with signal 11 |
| 6 | Runtime error | 249 ms | 159108 KB | Execution killed with signal 11 |
| 7 | Runtime error | 296 ms | 159820 KB | Execution killed with signal 11 |
| 8 | Runtime error | 230 ms | 159564 KB | Execution killed with signal 11 |
| 9 | Runtime error | 268 ms | 159412 KB | Execution killed with signal 11 |
| 10 | Correct | 156 ms | 78612 KB | Output is correct |
| 11 | Runtime error | 179 ms | 159156 KB | Execution killed with signal 11 |
| 12 | Runtime error | 212 ms | 159124 KB | Execution killed with signal 11 |
| 13 | Runtime error | 270 ms | 159348 KB | Execution killed with signal 11 |
| 14 | Runtime error | 184 ms | 159000 KB | Execution killed with signal 11 |
| 15 | Runtime error | 216 ms | 159052 KB | Execution killed with signal 11 |
| 16 | Runtime error | 273 ms | 159112 KB | Execution killed with signal 11 |
| 17 | Runtime error | 243 ms | 159404 KB | Execution killed with signal 11 |
| 18 | Runtime error | 300 ms | 159512 KB | Execution killed with signal 11 |
| 19 | Runtime error | 152 ms | 159072 KB | Execution killed with signal 11 |
| 20 | Runtime error | 285 ms | 159416 KB | Execution killed with signal 11 |
| 21 | Runtime error | 206 ms | 159152 KB | Execution killed with signal 11 |
| 22 | Runtime error | 292 ms | 159888 KB | Execution killed with signal 11 |
| 23 | Runtime error | 158 ms | 159308 KB | Execution killed with signal 11 |
| 24 | Correct | 218 ms | 78796 KB | Output is correct |
| 25 | Runtime error | 205 ms | 159124 KB | Execution killed with signal 11 |
| 26 | Correct | 257 ms | 78744 KB | Output is correct |
| 27 | Runtime error | 294 ms | 160012 KB | Execution killed with signal 11 |
| 28 | Correct | 253 ms | 78868 KB | Output is correct |
| 29 | Runtime error | 282 ms | 159860 KB | Execution killed with signal 11 |
| 30 | Runtime error | 238 ms | 159636 KB | Execution killed with signal 11 |
| 31 | Runtime error | 149 ms | 159084 KB | Execution killed with signal 11 |
| 32 | Correct | 261 ms | 78896 KB | Output is correct |
| 33 | Runtime error | 134 ms | 159116 KB | Execution killed with signal 11 |
| 34 | Runtime error | 243 ms | 159884 KB | Execution killed with signal 11 |
| 35 | Runtime error | 186 ms | 159052 KB | Execution killed with signal 11 |
| 36 | Correct | 438 ms | 79196 KB | Output is correct |
| 37 | Runtime error | 180 ms | 159820 KB | Execution killed with signal 11 |
| 38 | Runtime error | 250 ms | 159072 KB | Execution killed with signal 11 |
| 39 | Runtime error | 151 ms | 159052 KB | Execution killed with signal 11 |
| 40 | Runtime error | 193 ms | 159232 KB | Execution killed with signal 11 |
| 41 | Correct | 220 ms | 79112 KB | Output is correct |
| 42 | Runtime error | 237 ms | 159100 KB | Execution killed with signal 11 |