NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #193537 | #2726. 8.3t4 | wosile | 100 | 785ms | 121500kb | C++ | 534b | 2023-10-14 10:49:58 | 2023-10-14 12:48:19 |
answer
#include<bits/stdc++.h>
using namespace std;
int a[100005],ans[100005][305];
int n;
int dfs(int p,int k){
if(p>n)return 0;
if(ans[p][k]>0)return ans[p][k];
return ans[p][k]=dfs(p+a[p]+k,k)+1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int m;
scanf("%d",&m);
while(m--){
int p,k;
scanf("%d%d",&p,&k);
if(k>300){
int cnt=0;
while(p<=n){
cnt++;
p=p+a[p]+k;
}
printf("%d\n",cnt);
}
else printf("%d\n",dfs(p,k));
}
//quod erat demonstrandum
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1308kb
input:
100 5 6 12 22 23 21 22 7 30 5 22 22 29 30 30 10 7 17 25 24 1 16 17 30 3 19 7 27 14 20 28 5 22 23 13 ...
output:
3 7 5 3 2 2 3 4 3 3 4 3 3 4 5 4 2 5 2 5 5 3 4 5 3 3 4 5 4 2 2 2 4 3 2 6 2 5 3 4 2 3 3 2 2 3 2 2 3 3 ...
result:
ok 100 lines
Test #2:
score: 10
Accepted
time: 55ms
memory: 28520kb
input:
100000 25 29 13 9 17 27 2 5 20 4 27 25 5 24 17 13 13 14 3 13 4 24 19 9 21 20 14 17 9 11 13 9 5 24 20...
output:
6391 6391 6393 6386 6388 6393 6391 6393 6391 6392 6392 6390 6392 6392 6318 6395 6394 6389 6389 6390 ...
result:
ok 100000 lines
Test #3:
score: 10
Accepted
time: 62ms
memory: 28872kb
input:
100000 16 18 28 7 16 2 30 19 30 28 17 8 8 16 16 3 11 19 29 7 9 27 6 27 27 28 29 3 18 27 5 29 14 15 2...
output:
6477 6480 6475 6477 6475 6476 6478 6478 6319 6477 6479 6479 6479 6375 6353 6349 6476 6480 6480 6474 ...
result:
ok 100000 lines
Test #4:
score: 10
Accepted
time: 66ms
memory: 28788kb
input:
100000 29 30 15 26 1 29 1 4 12 22 12 4 9 27 20 29 21 8 29 27 11 5 13 7 20 15 5 15 10 1 30 28 10 30 3...
output:
6475 6475 6472 6468 6473 6469 6472 6473 6472 6478 6469 6469 6476 6470 6474 6473 6470 6469 6470 6475 ...
result:
ok 100000 lines
Test #5:
score: 10
Accepted
time: 59ms
memory: 28940kb
input:
100000 30 25 29 4 13 25 14 15 21 20 8 4 17 16 13 8 10 17 21 10 14 13 9 26 28 14 28 13 29 10 28 2 3 1...
output:
6484 6483 6481 6487 6483 6487 6480 6484 6484 6483 6482 6486 6486 6374 6483 6484 6480 6483 6480 6482 ...
result:
ok 100000 lines
Test #6:
score: 10
Accepted
time: 113ms
memory: 120956kb
input:
100000 3 1 9 1 7 6 10 9 5 10 6 5 5 8 2 8 10 1 9 4 4 3 6 3 1 9 5 2 7 8 1 3 8 6 1 8 3 1 1 10 8 4 2 8 5...
output:
15308 13281 11724 10574 9488 8665 8036 7431 6893 6485 6049 5722 5409 5128 4872 4655 4441 4242 4085 3...
result:
ok 100000 lines
Test #7:
score: 10
Accepted
time: 127ms
memory: 120812kb
input:
100000 19 6 20 1 19 14 23 14 23 3 9 1 14 19 22 21 4 26 2 20 16 9 27 20 23 2 19 5 13 18 6 11 17 13 9 ...
output:
6114 5717 5377 5141 4930 4672 4418 4263 4061 3903 3782 3655 3495 3376 3278 3161 3065 2986 2897 2793 ...
result:
ok 100000 lines
Test #8:
score: 10
Accepted
time: 78ms
memory: 120808kb
input:
100000 3 16 18 2 10 29 27 26 12 11 15 12 29 16 2 8 14 4 28 13 21 13 2 24 4 9 16 14 4 27 27 15 18 13 ...
output:
6080 5669 5408 5099 4853 4700 4382 4228 4073 3908 3757 3632 3491 3369 3273 3181 3049 2989 2913 2818 ...
result:
ok 100000 lines
Test #9:
score: 10
Accepted
time: 97ms
memory: 120592kb
input:
100000 82 65 27 36 67 74 9 74 35 72 97 28 57 78 88 66 89 20 30 50 2 1 19 8 97 4 47 37 6 73 22 31 64 ...
output:
1926 1906 1818 1831 1806 1746 1765 1700 1691 1623 1624 1621 1575 1549 1524 1505 1442 1471 1430 1424 ...
result:
ok 100000 lines
Test #10:
score: 10
Accepted
time: 128ms
memory: 121500kb
input:
100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
50000 33333 25000 20000 16667 14286 12500 11112 10000 9091 8334 7693 7143 6667 6250 5883 5556 5264 5...
result:
ok 100000 lines
