| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 199451 | 2020-02-01T12:52:28 Z | TadijaSebez | Brunhilda’s Birthday (BOI13_brunhilda) | C++11 | 555 ms | 120692 KB |
#include <bits/stdc++.h>
using namespace std;
const int N=10000050;
const int Q=100050;
int dp[N],fir[N],go[Q],p[Q],n[Q],cnt[N],ptr;
void Add(int x,int i){go[i]=fir[x];fir[x]=i;}
int main(){
int m,q;
scanf("%i %i",&m,&q);
for(int i=1;i<=m;i++)scanf("%i",&p[i]),Add(p[i],i),cnt[0]++;
for(int i=1;i<N;i++){
for(int id=fir[i],nxt;id;id=nxt){
cnt[i-p[id]]--;
cnt[i]++;
nxt=go[id];
if(i+p[id]<N)Add(i+p[id],id);
}
while(cnt[ptr]==0)ptr++;
if(ptr==i){
for(;i<N;i++)dp[i]=1e9;
break;
}
dp[i]=dp[ptr]+1;
}
for(int i=1;i<=q;i++){
scanf("%i",&n[i]);
if(dp[n[i]]==1e9)printf("oo\n");
else printf("%i\n",dp[n[i]]);
}
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 31 ms | 39544 KB | Output is correct |
| 2 | Correct | 161 ms | 117752 KB | Output is correct |
| 3 | Correct | 35 ms | 41592 KB | Output is correct |
| 4 | Correct | 97 ms | 117884 KB | Output is correct |
| 5 | Correct | 135 ms | 117880 KB | Output is correct |
| 6 | Correct | 32 ms | 39544 KB | Output is correct |
| 7 | Correct | 34 ms | 41592 KB | Output is correct |
| 8 | Correct | 44 ms | 46584 KB | Output is correct |
| 9 | Correct | 234 ms | 117752 KB | Output is correct |
| 10 | Correct | 239 ms | 117752 KB | Output is correct |
| 11 | Correct | 205 ms | 117752 KB | Output is correct |
| 12 | Correct | 94 ms | 117752 KB | Output is correct |
| 13 | Correct | 301 ms | 117728 KB | Output is correct |
| 14 | Correct | 310 ms | 117880 KB | Output is correct |
| 15 | Correct | 182 ms | 117788 KB | Output is correct |
| 16 | Correct | 162 ms | 117752 KB | Output is correct |
| 17 | Correct | 134 ms | 117880 KB | Output is correct |
| 18 | Correct | 101 ms | 117884 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 186 ms | 118008 KB | Output is correct |
| 2 | Correct | 218 ms | 119160 KB | Output is correct |
| 3 | Correct | 508 ms | 118904 KB | Output is correct |
| 4 | Correct | 183 ms | 117792 KB | Output is correct |
| 5 | Correct | 398 ms | 118520 KB | Output is correct |
| 6 | Correct | 160 ms | 117752 KB | Output is correct |
| 7 | Correct | 197 ms | 117880 KB | Output is correct |
| 8 | Correct | 163 ms | 117752 KB | Output is correct |
| 9 | Correct | 420 ms | 118856 KB | Output is correct |
| 10 | Correct | 447 ms | 118752 KB | Output is correct |
| 11 | Correct | 441 ms | 118300 KB | Output is correct |
| 12 | Correct | 238 ms | 117700 KB | Output is correct |
| 13 | Correct | 171 ms | 117784 KB | Output is correct |
| 14 | Correct | 184 ms | 117828 KB | Output is correct |
| 15 | Correct | 435 ms | 118368 KB | Output is correct |
| 16 | Correct | 216 ms | 119136 KB | Output is correct |
| 17 | Correct | 313 ms | 117872 KB | Output is correct |
| 18 | Correct | 427 ms | 119280 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 475 ms | 119108 KB | Output is correct |
| 2 | Correct | 508 ms | 118904 KB | Output is correct |
| 3 | Correct | 492 ms | 119492 KB | Output is correct |
| 4 | Correct | 310 ms | 119168 KB | Output is correct |
| 5 | Correct | 298 ms | 120672 KB | Output is correct |
| 6 | Correct | 369 ms | 119160 KB | Output is correct |
| 7 | Correct | 379 ms | 120036 KB | Output is correct |
| 8 | Correct | 450 ms | 119036 KB | Output is correct |
| 9 | Correct | 493 ms | 119032 KB | Output is correct |
| 10 | Correct | 252 ms | 118096 KB | Output is correct |
| 11 | Correct | 216 ms | 118140 KB | Output is correct |
| 12 | Correct | 317 ms | 118112 KB | Output is correct |
| 13 | Correct | 435 ms | 119544 KB | Output is correct |
| 14 | Correct | 281 ms | 119544 KB | Output is correct |
| 15 | Correct | 337 ms | 118196 KB | Output is correct |
| 16 | Correct | 342 ms | 118136 KB | Output is correct |
| 17 | Correct | 302 ms | 118648 KB | Output is correct |
| 18 | Correct | 511 ms | 118904 KB | Output is correct |
| 19 | Correct | 202 ms | 118136 KB | Output is correct |
| 20 | Correct | 517 ms | 119344 KB | Output is correct |
| 21 | Correct | 299 ms | 119612 KB | Output is correct |
| 22 | Correct | 555 ms | 120636 KB | Output is correct |
| 23 | Correct | 259 ms | 119772 KB | Output is correct |
| 24 | Correct | 155 ms | 119160 KB | Output is correct |
| 25 | Correct | 306 ms | 119216 KB | Output is correct |
| 26 | Correct | 272 ms | 119032 KB | Output is correct |
| 27 | Correct | 466 ms | 120020 KB | Output is correct |
| 28 | Correct | 177 ms | 119288 KB | Output is correct |
| 29 | Correct | 413 ms | 120692 KB | Output is correct |
| 30 | Correct | 446 ms | 120184 KB | Output is correct |
| 31 | Correct | 230 ms | 119136 KB | Output is correct |
| 32 | Correct | 244 ms | 119160 KB | Output is correct |
| 33 | Correct | 181 ms | 119032 KB | Output is correct |
| 34 | Correct | 334 ms | 119960 KB | Output is correct |
| 35 | Correct | 178 ms | 119288 KB | Output is correct |
| 36 | Correct | 531 ms | 120440 KB | Output is correct |
| 37 | Correct | 294 ms | 120568 KB | Output is correct |
| 38 | Correct | 343 ms | 119288 KB | Output is correct |
| 39 | Correct | 196 ms | 119224 KB | Output is correct |
| 40 | Correct | 313 ms | 119288 KB | Output is correct |
| 41 | Correct | 380 ms | 120056 KB | Output is correct |
| 42 | Correct | 346 ms | 119544 KB | Output is correct |