| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 631360 | 2022-08-18T03:43:35 Z | uylulu | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 379 ms | 159920 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] = 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 | 34 ms | 39392 KB | Output is correct |
| 2 | Runtime error | 160 ms | 159028 KB | Execution killed with signal 11 |
| 3 | Correct | 39 ms | 40460 KB | Output is correct |
| 4 | Runtime error | 135 ms | 159052 KB | Execution killed with signal 11 |
| 5 | Correct | 84 ms | 78464 KB | Output is correct |
| 6 | Correct | 36 ms | 39508 KB | Output is correct |
| 7 | Correct | 43 ms | 40400 KB | Output is correct |
| 8 | Correct | 46 ms | 42968 KB | Output is correct |
| 9 | Runtime error | 185 ms | 159068 KB | Execution killed with signal 11 |
| 10 | Runtime error | 190 ms | 159116 KB | Execution killed with signal 11 |
| 11 | Correct | 100 ms | 78468 KB | Output is correct |
| 12 | Runtime error | 131 ms | 159112 KB | Execution killed with signal 11 |
| 13 | Runtime error | 256 ms | 159052 KB | Execution killed with signal 11 |
| 14 | Runtime error | 255 ms | 159096 KB | Execution killed with signal 11 |
| 15 | Correct | 86 ms | 78452 KB | Output is correct |
| 16 | Runtime error | 173 ms | 159060 KB | Execution killed with signal 11 |
| 17 | Runtime error | 151 ms | 159108 KB | Execution killed with signal 11 |
| 18 | Runtime error | 138 ms | 159020 KB | Execution killed with signal 11 |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 153 ms | 159160 KB | Execution killed with signal 11 |
| 2 | Correct | 100 ms | 78848 KB | Output is correct |
| 3 | Runtime error | 301 ms | 159680 KB | Execution killed with signal 11 |
| 4 | Runtime error | 167 ms | 159052 KB | Execution killed with signal 11 |
| 5 | Runtime error | 232 ms | 159436 KB | Execution killed with signal 11 |
| 6 | Correct | 92 ms | 78468 KB | Output is correct |
| 7 | Runtime error | 143 ms | 159164 KB | Execution killed with signal 11 |
| 8 | Runtime error | 164 ms | 159044 KB | Execution killed with signal 11 |
| 9 | Runtime error | 264 ms | 159636 KB | Execution killed with signal 11 |
| 10 | Runtime error | 309 ms | 159616 KB | Execution killed with signal 11 |
| 11 | Runtime error | 296 ms | 159516 KB | Execution killed with signal 11 |
| 12 | Runtime error | 184 ms | 159112 KB | Execution killed with signal 11 |
| 13 | Runtime error | 132 ms | 159104 KB | Execution killed with signal 11 |
| 14 | Runtime error | 173 ms | 159112 KB | Execution killed with signal 11 |
| 15 | Runtime error | 248 ms | 159400 KB | Execution killed with signal 11 |
| 16 | Correct | 95 ms | 78868 KB | Output is correct |
| 17 | Runtime error | 255 ms | 159044 KB | Execution killed with signal 11 |
| 18 | Correct | 185 ms | 78856 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 274 ms | 159432 KB | Execution killed with signal 11 |
| 2 | Runtime error | 332 ms | 159472 KB | Execution killed with signal 11 |
| 3 | Runtime error | 293 ms | 159480 KB | Execution killed with signal 11 |
| 4 | Correct | 258 ms | 78832 KB | Output is correct |
| 5 | Runtime error | 177 ms | 159888 KB | Execution killed with signal 11 |
| 6 | Runtime error | 250 ms | 159112 KB | Execution killed with signal 11 |
| 7 | Runtime error | 259 ms | 159920 KB | Execution killed with signal 11 |
| 8 | Runtime error | 245 ms | 159420 KB | Execution killed with signal 11 |
| 9 | Runtime error | 255 ms | 159424 KB | Execution killed with signal 11 |
| 10 | Correct | 160 ms | 78496 KB | Output is correct |
| 11 | Runtime error | 183 ms | 159044 KB | Execution killed with signal 11 |
| 12 | Runtime error | 244 ms | 159072 KB | Execution killed with signal 11 |
| 13 | Runtime error | 293 ms | 159348 KB | Execution killed with signal 11 |
| 14 | Runtime error | 189 ms | 159104 KB | Execution killed with signal 11 |
| 15 | Runtime error | 231 ms | 159144 KB | Execution killed with signal 11 |
| 16 | Runtime error | 261 ms | 159104 KB | Execution killed with signal 11 |
| 17 | Runtime error | 259 ms | 159416 KB | Execution killed with signal 11 |
| 18 | Runtime error | 328 ms | 159548 KB | Execution killed with signal 11 |
| 19 | Runtime error | 146 ms | 159056 KB | Execution killed with signal 11 |
| 20 | Runtime error | 315 ms | 159432 KB | Execution killed with signal 11 |
| 21 | Runtime error | 227 ms | 159064 KB | Execution killed with signal 11 |
| 22 | Runtime error | 303 ms | 159876 KB | Execution killed with signal 11 |
| 23 | Runtime error | 205 ms | 159252 KB | Execution killed with signal 11 |
| 24 | Correct | 210 ms | 78804 KB | Output is correct |
| 25 | Runtime error | 215 ms | 159024 KB | Execution killed with signal 11 |
| 26 | Correct | 263 ms | 78896 KB | Output is correct |
| 27 | Runtime error | 316 ms | 159856 KB | Execution killed with signal 11 |
| 28 | Correct | 235 ms | 78824 KB | Output is correct |
| 29 | Runtime error | 294 ms | 159884 KB | Execution killed with signal 11 |
| 30 | Runtime error | 258 ms | 159560 KB | Execution killed with signal 11 |
| 31 | Runtime error | 164 ms | 159052 KB | Execution killed with signal 11 |
| 32 | Correct | 253 ms | 78784 KB | Output is correct |
| 33 | Runtime error | 136 ms | 159124 KB | Execution killed with signal 11 |
| 34 | Runtime error | 250 ms | 159880 KB | Execution killed with signal 11 |
| 35 | Runtime error | 147 ms | 159132 KB | Execution killed with signal 11 |
| 36 | Correct | 379 ms | 79080 KB | Output is correct |
| 37 | Runtime error | 176 ms | 159820 KB | Execution killed with signal 11 |
| 38 | Runtime error | 232 ms | 159088 KB | Execution killed with signal 11 |
| 39 | Runtime error | 144 ms | 159112 KB | Execution killed with signal 11 |
| 40 | Runtime error | 209 ms | 159100 KB | Execution killed with signal 11 |
| 41 | Correct | 235 ms | 79056 KB | Output is correct |
| 42 | Runtime error | 250 ms | 159128 KB | Execution killed with signal 11 |